#P1295D. Same GCDs
-
ID: 5183
Type: RemoteJudge
2000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Same GCDs
No submission language available for this problem.
Description
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.
Input
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}$).
Output
Print $T$ integers — one per test case. For each test case print the number of appropriate $x$-s.
Samples
3
4 9
5 10
42 9999999967
6
1
9999999966
Note
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$.