Migrated from Lutece 447 T-Residual Set

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Given a pair of number $(p,t)$ where $p$ is a prime and $t$ is a non-negative integer.

The Residual Set of any prime number $p$ is all the integers between $1$ and $p-1$,

that is, $1, 2, 3, 4, \cdots, p-2, p-1$.

What's more, a T-Residual Set of any prime number p means the set of integers below:

$1^T\ mod\ p, 2^T\ mod\ p, 3^T\ mod\ p, 4^T\ mod\ p, \cdots (p-2)^T\ mod \ p, (p-1)^T\ mod \ p$, where $T$ must be non-negative.

Now for each pair of $(p,t)$, you should calculate how many distinct numbers there are in the t-Residual Set of $p$.

Input

A number $T$ ($T\leq 10^6$) in first line.

Then $T$ test cases follow.

Each Test case contains two number $p$ ($0<p<10^8$) and $t$ ($0<t<2^{31}$),

which meanings areaccording to the description.

Output

Output $T$ lines.

Each line contains one number, refers to the answer.

Samples

3
7 9
17 89
47 56

2
16
23

Resources

5th BUPT Programming Contest Final