CF1295D.Same GCDs

You are given two integers $a$ and $m$. Calculate the number of integers $x$ such that $0 \le x \lt m$ and $\gcd(a, m) = \gcd(a + x, m)$.

Note: $\gcd(a, b)$ is the greatest common divisor of $a$ and $b$.

给你两个整数 $a$ 和 $m$。请计算满足 $0 \le x < m$ 且 $\gcd(a, m) = \gcd(a + x, m)$ 的整数 $x$ 的个数。

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

The first line contains the single integer $T$ ($1 \le T \le 50$) — the number of test cases.

Next $T$ lines contain test cases — one per line. Each line contains two integers $a$ and $m$ ($1 \le a \lt m \le 10^{10}$).

第一行包含一个整数 $T$（$1 \le T \le 50$）—— 测试用例的数量。

接下来的 $T$ 行为测试用例，每行一个测试用例。每行包含两个整数 $a$ 和 $m$（$1 \le a \lt m \le 10^{10}$）。

Print $T$ integers — one per test case. For each test case print the number of appropriate $x$-s.

输出 $T$ 个整数——每个测试用例输出一个整数。对于每个测试用例，输出满足条件的 $x$ 的个数。

In the first test case appropriate $x$-s are $[0, 1, 3, 4, 6, 7]$.

In the second test case the only appropriate $x$ is $0$.

在第一个测试用例中，合适的 $x$ 值为 $[0, 1, 3, 4, 6, 7]$。

在第二个测试用例中，唯一的合适 $x$ 值为 $0$。