Problem Description

Answer the following $ Q $ queries.

Given integers $ A_i, M_i $. Determine if there exists a positive integer $ K_i $ less than or equal to $2 \times 10^{18}$ such that $A_i^{K_i} \equiv K_i \pmod{M_i}$. If it exists, find one.

Input Format

The input is given from the standard input in the following format:

$ Q $ $ A_1 $ $ M_1 $ : $ A_Q $ $ M_Q $

Output Format

On the $ i $-th line, output $ -1 $ if there is no $ K_i $ that satisfies the condition for the $ i $-th query. Otherwise, output one such $ K_i $ that satisfies $A_i^{K_i} \equiv K_i \pmod{M_i}$ and is less than or equal to $2 \times 10^{18}$. If there are multiple possible answers, you may output any one of them.

Sample Input and Output

Sample Input #1

4
2 4
3 8
9 6
10 7

Sample Output #1

4
11
9
2

Sample Input #2

3
177 168
2028 88772
123456789 987654321

Sample Output #2

7953
234831584
471523108231963269

Notes/Hints

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)$

Sample Explanation 1

Each satisfies the condition: $2^4 = 16 \equiv 4 \pmod{4}$, $3^{11} = 177147 \equiv 11 \pmod{8}$, $9^9 = 387420489 \equiv 9 \pmod{6}$, $10^2 = 100 \equiv 2 \pmod{7}$.

见题面 Input 部分

见题面 Output 部分