Gats and the Resonant Jump

Time limit: 3000 msMemory limit: 64 MB

Gats is standing beside a circular track containing $N$ stones labeled $0,1,\ldots,N-1$ .

If Gats starts on stone $X$ , one jump of length $K$ takes him to stone

Y = (X + K) \bmod N.

The tuning value of a stone labeled $Z$ is $\gcd(Z,N)$ . In particular, the tuning value of stone $0$ is $\gcd(0,N)=N$ .

A starting stone $X$ is called resonant if its tuning value is unchanged by the jump, meaning

\gcd(X,N)=\gcd(Y,N).

For each test case, determine how many of the $N$ possible starting stones are resonant.

Input

The first line contains an integer $T$ ( $1 \le T \le 500$ ), the number of test cases.

Each of the next $T$ lines contains two integers $N$ and $K$ (, ), the number of stones and the jump length.

Output

For each test case, print one integer: the number of resonant starting stones.

Samples

Sample 1

Input

Output

For $(N,K)=(5,1)$ , the resonant starting stones are $X \in \{1,2,3\}$ . For , they are . For , they are . For , every stone except and is resonant. In the final test case, the jump returns Gats to the starting stone, so every stone is resonant.

Gats and the Resonant Jump

Input

Output

Samples

Sample 1

Submit

Submissions