给你两个整数 $$$a$$$ 和 $$$m$$$。计算满足 $$$0 \le x < m$$$ 且 $$$\gcd(a, m) = \gcd(a + x, m)$$$ 的整数个数 $$$x$$$。
注意:$$$\gcd(a, b)$$$ 是$$$a$$$ 和$$$b$$$ 的最大公约数。
输入
第一行包含单个整数 $$$T$$$ ($$$1 \le T \le 50$$$) — 测试用例的数量。
接下来的 $$$T$$$ 行包含测试用例 - 每行一个。每行包含两个整数 $$$a$$$ 和 $$$m$$$ ($$$1 \le a < m \le 10^{10}$$$)。
输出
打印 $$$T$$$ 整数 — 每个测试用例一个。对于每个测试用例,打印适当的 $$$x$$$-s 的数量。
示例
输入 #1
3 4 9 5 10 42 9999999967
输出 #1
6 1 9999999966
注意
在第一个测试用例中,适当的 $$$x$$$-s 是 $$$[0, 1, 3, 4, 6, 7]$$$。
在第二个测试用例中,唯一合适的 $$$x$$$ 是 $$$0$$$。