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.
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).
For each testcase, print a single line with the number of co-primes for the corresponding testcase.
Input | Output |
---|---|
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). |