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

见题面

见题面