#OJ1517. Time Limit: 1 Sec Memory Limit: 128 MB
Time Limit: 1 Sec Memory Limit: 128 MB
Time Limit: 1 Sec Memory Limit: 128 MB
Description
两个正整数a,b最大公约数GCD(a,b),一般也被写成(a,b),例如(1,2) = 1,(12,6)=6. GCD很容易用欧几里得算法求得。 但是现在有一个新的问题:给定两个正整数N,M,问有多少个正整数X满足: 1<=X<=N,并且(X,N)>= M.
Input
多组测试数据。输入第一行一个数T<=3000,表示测试数据组数。 接下来的T组测试数据,每组一行,每行两个正整数N和M(1 <= 1000000000,1 <= M <= 1000000000)。
Output
每组测试数据输出X的个数,占一行。
Sample Input
3
1 1
10 2
10000 72
Sample Output
1
6
260