D. 相同 GCD 计数

时间限制：$2$ 秒
内存限制：$256$ 兆字节

给定两个整数 $a$ 和 $m$。
请计算满足下面条件的整数 $x$ 的个数：

$$0\le x<m \quad \text{且} \quad \gcd(a,m)=\gcd(a+x,m) $$

注：$\gcd(a,b)$ 表示 $a$ 和 $b$ 的最大公约数。

---

输入格式

第一行一个整数 $T$（$1\le T\le 50$），表示测试用例组数。

接下来 $T$ 行，每行两个整数 $a$ 和 $m$（$1\le a<m\le 10^{10}$）。

---

输出格式

输出 $T$ 行，每行一个整数，表示对应测试用例的合法 $x$ 的数量。

---

样例输入

3
4 9
5 10
42 9999999967

样例输出

6
1
9999999966

---

说明

在第一个样例中，合法的 $x$ 是：$[0,1,3,4,6,7]$。

在第二个样例中，唯一合法的 $x$ 是 $0$。