CF1295D Same GCDs

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

在第一个测试用例中，满足条件的 $x$ 有 $[0, 1, 3, 4, 6, 7]$。 在第二个测试用例中，唯一满足条件的 $x$ 是 $0$。 由 ChatGPT 4.1 翻译