Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Fast Co-Prime

By himuhasib · 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).



Discussion
Statistics

58% Solution Ratio

Maruf_75Earliest, Jan '17

prodip_bsmrstuFastest, 0.0s

ovis96Lightest, 131 kB

mdvirusShortest, 347B

Submit

Login to submit