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).


Submit

Login to submit.

Contributors

Statistics

63% Solution Ratio
Sherlock221bEarliest, Jun '16
JIANEEFastest, 0.0s
riadroxLightest, 0 B
Nusab19Shortest, 178B
Toph uses cookies. By continuing you agree to our Cookie Policy.