M. *【模拟】关于GCD的问题

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

设 $a,b$ 的最大公约数可以通过函数 $\gcd(a,b)$ 求得。

给出两个数 $n,m$ ，求 $x$ 的个数 $(x$ 满足 $1 \le x \le n , \gcd(x,n) \ge m)$ 。

第一行为一个正整数 $t$ ，表示有t组测试数据。

每组测试数据一行，两个非负整数 $n,m( 0 \le n,m \le 10^6)$ 。

每组数据输出一行一个整数，即 $x$ 的个数。

1
6
260