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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define SF scanf
#define PF printf
using namespace std;
long long power(long long x,long long num,long long mod){
    long long res=1;
    while(num){
        if(num&1){res=res*x;res%=mod;}
        x*=x;
        x%=mod;
        num>>=1;
    }
    return res;
}
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 x,long long y){
    if(y==0)
        return x;
    return gcd(y,x%y);
}
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 mod){
    if(mod==1)
        return 1;
    long long x,y;
    long long pm=phi(mod);
    long long d=gcd(mod,pm);
    long long t=solve(a,d);
    long long at=power(a,t,mod);
    exgcd(mod/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*mod+at;
}
long long a,mod;
int main(){
    int q;
    SF("%d",&q);
    while(q--){
        SF("%lld%lld",&a,&mod);
        PF("%lld\n",solve(a,mod));
    }
}
