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$ 的个数。

样例 #1

样例输入

3
4 9
5 10
42 9999999967

样例输出

6
1
9999999966

说明/提示

在第一个测试用例中，满足条件的 $x$ 有 $[0, 1, 3, 4, 6, 7]$。

在第二个测试用例中，唯一满足条件的 $x$ 是 $0$。

由 ChatGPT 4.1 翻译