CF1295D.Same GCDs

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

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

Note: $\gcd(a, b)$ is the greatest common divisor of $a$ and $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 < m \le 10^{10}$ ).

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

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$ .