Migrated from Lutece 476 最大公约数

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

两个正整数$a,b$最大公约数 $\gcd(a,b)$，一般也被写成 $(a,b)$，例如 $(1,2) = 1,(12,6)=6$.

$\gcd$ 很容易用欧几里得算法求得。但是现在有一个新的问题：给定两个正整数 $N,M$，问有多少个正整数 $X$ 满足： $1\leq X\leq N$ 并且 $(X,N)\geq M$。

Input

第一行为测试数据个数：$T$, $T\leq 3000$;

接下来的$T$组测试数据，每组一行，每行两个正整数$N$和$M$（$1\leq N,M \leq 10^9$）。

Output

输出$x$的个数，占一行。

Samples

3
1 1
10 2
10000 72

1
6
260

Resources

recommend by liverliu