Problem Statement

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)

Inputs

Input is given from Standard Input in the following format:

Q
A_1 M_1
:
A_Q M_Q

Outputs

In the i-th line, print -1 if there is no integer K_i that satisfies the condition. Otherwise, print an integer K_i not exceeding 2 × 10^{18} such that A_i^{K_i} ≡ K_i (mod M_i). If there are multiple solutions, any of them will be accepted.

Sample Input 1

4
2 4
3 8
9 6
10 7

Sample Output 1

4
11
9
2

It can be seen that the condition is satisfied: 2^4 = 16 ≡ 4 (mod 4), 3^{11} = 177147 ≡ 11 (mod 8), 9^9 = 387420489 ≡ 9 (mod 6) and 10^2 = 100 ≡ 2 (mod 7).

Sample Input 2

3
177 168
2028 88772
123456789 987654321

Sample Output 2

7953
234831584
471523108231963269