Description:
The greatest common divisor GCD(a,b) of two positive integer a and b,sometimes written (a,b),
is the largest divisior common to a and b.For example,(1,2)=1,(12,18)=6;
(a,b) can be easily found by the Euclidean algorithm.Now Carp is considering a little more difficlut problem.
Given integer N and M,how many integer X satisfies 1<=X<=N and (X,N)
≥M.
Input:
The first line or input is an integer T(<=3000)representing the number of test cases.The following T lines each contains two numbers N and M(1<=N<=1000000000,0<=M<=1000000000),representing a test case.
Output:
For each test case,output the answer on a single line.
Sample Input:
3
1 1
10 2
10000 72
Sample Output:
1
6
260
Note:
本题由旧版NOJ导入,来源:第九届中山大学程序设计竞赛预选题