D. Same GCDs
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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.

Example
Input
3
4 9
5 10
42 9999999967
Output
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$$$.