A13221 | $Same GCDs$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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.

输入 #1

3
4 9
5 10
42 9999999967

输出 #1

6
1
9999999966

C++ 编辑器

输入

输出