Anubis is always playing with numbers. Recently he wanted to know how many numbers there are in the range [1, N] that are even and multiples of p. What about helping him? Write a program that automates this task.

Input

The first line of input contains T (1 <= T <= 100), the number of test cases. T lines follow. Each test case is fully contained in a single line. A test case is represented by two space-separated integers N (1 <= N <= 1024) and p (1 <= p <= N). 

Output

For each test case, output its answer in a single line. 

Example

Input:
1
10 5

Output:
1