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.
2 5 2 6 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 ).
himuhasibHasib 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. →