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 CPP):

Solution:
#include<cstdio>
long long modpow(long long a,long long b,long long p)
{
    long long ret=1;
    for(;b>0;b>>=1,a=(a*a)%p)
        if(b&1)
            ret=(ret*a)%p;
    return ret;
}
long long phi(long long n)
{
    long long res=n,t=n;
    for(long long i=2;i*i<=t;i++)
        if(t%i==0)
        {
            res-=res/i;
            while(t%i==0)
                t/=i;
        }
    if(t>1)
        res-=res/t;
    return res;
}
long long gcd(long long a,long long b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if(b==0)
    {x=1;y=0;return a;}
    long long g;
    g=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return g;
}
long long solve(long long A,long long M)
{
	if(M==1)
		return 1;
    /*if(M<=500)
    {
        long long s=A;
        for(long long i=1;;i++)
        {
            if(s==i%M)
                return i;
            s=(s*A)%M;
        }
    }*/
    long long pM,At,d,t,x,y;
    pM=phi(M);
    d=gcd(M,pM);
    t=solve(A,d);
    At=modpow(A,t,M);
    exgcd(M/d,pM/d,x,y);
    x=x*(((t-At)%pM+pM)%pM)/d;
    x=((x%(pM/d))+pM/d)%(pM/d)+pM/d;
    return x*M+At;
}
int main()
{
    int Q;
    long long A,M;
    scanf("%d",&Q);
    while(Q--)
    {
        scanf("%lld%lld",&A,&M);
        printf("%lld\n",solve(A,M));
    }
    return 0;
}