【普及】最大公约数计数

给定正整数 $n$ 和 $d$，请问 $1 \sim n$ 中有多少个数 $x$ 满足 $x$ 和 $n$ 的最大公约数是 $d$；

即求满足 $gcd(x, n) = d$ 的 $x$ 的个数。

输入格式

第一行，一个整数 $T$ 代表数据组数；接下来 $T$ 组数据

每组数据包含 $2$ 个正整数代表 $n$ 和 $d$

输出格式

对于每组数据输出一行，包含答案

1
12 2

2

提示

【样例 1 解释】

• $\gcd(2, 12) = 2, \gcd(10, 12)\ =\ 2$
• 其他数不满足，比如 $\gcd(8, 12)\ =\ 4$

【数据范围】

• $1 \le T \le 10^6$
• $1 \le d \le n \le 10^6$

来源

• acwing_873：欧拉函数
• acwing_874：筛法求欧拉函数