← 返回题目列表

Codeforces · 1295/D

D. 相同的 GCD

中文机器翻译题面 查看原题

给你两个整数 $$$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$$$。