GCD

Problem Description

Given integers $a$ and $m$, count the number of integers $x$ satisfying $0 \le x < m$ and $\gcd(a, m) = \gcd(a + x, m)$.

Input Format

The first line contains an integer $T$.

The next $T$ lines each contain two integers $a, m$.

Output Format

Output $T$ lines, each containing a single integer: the answer.

Sample Input

3
4 9
5 10
42 9999999967

Sample Output

6
1
9999999966

Constraints

$1 \le T \le 50$, $1 \le a < m \le 10^{10}$.