A13221. Same GCDs
编程题
普及/提高-
知识点
题目描述
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$ .
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}$ ).
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.
输入输出样例
输入 #1
3 4 9 5 10 42 9999999967
输出 #1
6 1 9999999966
说明/提示
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$ .
In the second test case the only appropriate $x$ is $0$ .