Fast Co-Prime

Limits 1s, 512 MB

Two numbers A and B are called co-prime if the only common positive factor of the two numbers is 1.

You are given two positive integers N and K, you have to find out how many numbers from N to N×K are co-prime with N.

Input

The first line contains T (1 ≤ T ≤ 100), the number of testcases.

Each of the next T lines contain two space separated integers, N (2 ≤ N ≤ 1000000000) and K (1 ≤ K ≤ 1000).

Output

For each testcase, print a single line with the number of co-primes for the corresponding testcase.

Sample

InputOutput
2
5 2
6 2

4
2

For the first input, 6, 7, 8, 9 are co-prime with 5 in the range (5, 10).

For the second input, only 7 and 11 are co-prime with 6 in the range (6, 12).