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

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.

Samples

InputOutput
2
5 2
6 2
4
2

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

Only 7 and 11 are co-prime with 6 in the range ( 6, 12 ).

Author
  • himuhasib's Avatar

    himuhasib

    Hasib is passionate about sport programming and artificial intelligence. He was an IOI participant through years 2013-2015. He qualified to ACM-ICPC World Finals 2016. He studies at North South University.
Discussion
Submit

Login to submit