"Promises are meant to be broken."
Chotu being desperately in love with her crush made N promises to her on Promise Day. Each promise "i" is associated with an effort value Ei. The effort value of all the promises are distinct and each Effort value lies between 1 to N (both inclusive).
It was later he realised that he will not be able to fulfil all the N promises he made. After analysing all the N promises he came to a conclusion that he can only fulfil a promise "i" if and only if GCD(Ei, N) = D. Find out how many promises will Chotu be able to fulfil.
NOTE :
GCD(x, y) means the highest common factor that divides both x and y.
Input
First line of input contains the number T denoting number of test cases.
Each of the next T lines contain 2 space separated integers N and D
Output
Print T lines. Each containing a single integer denoting number Promises Chotu can make.
Constrains
1 <= T <= 1000
1 <= D <= N <= 106
For the first sample case, GCD of (1, 5), (2, 5), (3, 5), (4, 5) is 1.
For the second sample case, no number has GCD = 3 with 10.
