Problem: 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

Solution (in PYTHON3):

Solution:
from math import gcd
def euler_phi(n):
    res=n
    for x in range(2,int(n**.5)+2):
        if n%x==0:
            res=(res//x)*(x-1)
            while n%x==0:
                n//=x
    if n!=1:
        res=(res//n)*(n-1)
    return res

def biggcd(n,m):
    g=gcd(n,m);res=g;count=2
    while gcd(g**count,m)>res:
        res=gcd(g**count,m)
        count+=1
    return res

def solve(a,m,n):
    if gcd(a,m)==1:
        if m==1: return 1
        phi=euler_phi(m);G=gcd(phi,m);r0=solve(a,G,n);mod=m*phi//G
        return ((((pow(a,n*r0,mod)-n*r0)%mod)//G)*pow(n*phi//G,phi-1,m)*phi+r0)%mod
    big=biggcd(a,m);k0=solve(a,m//big,n*big)
    return big*k0

for i in range(int(input())):
    A,M=map(int,input().split())
    print(solve(A,M,1))