ModularPowerEquation!!

Process the Q queries below.

• You are given two integers A_i and M_i. Determine whether there exists a positive integer K_i not exceeding 2 × 10^{18} such that A_i^{K_i} ≡ K_i (mod M_i), and find one if it exists.

Constraints

• 1 \leq Q \leq 100
• 0 \leq A_i \leq 10^9(1 \leq i \leq Q)
• 1 \leq M_i \leq 10^9(1 \leq i \leq Q)

Examples

Input

4 2 4 3 8 9 6 10 7

Output

4 11 9 2

Input

3 177 168 2028 88772 123456789 987654321

Output

7953 234831584 471523108231963269

inputFormat

Input

4 2 4 3 8 9 6 10 7

outputFormat

Output

4 11 9 2

Input

3 177 168 2028 88772 123456789 987654321

Output

7953 234831584 471523108231963269

样例

3
177 168
2028 88772
123456789 987654321

7953
234831584
471523108231963269

</p>