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 <bits/stdc++.h>
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
typedef pair <ll, ll> P;
map<ll, ll> prime_factor(ll n){
    map<ll, ll> res;
    for (ll i=2; i*i<=n; i++){
        while(n%i==0){
            ++res[i];
            n/=i;
        }
    }
    if (n!=1) res[n]=1;
    return res;
}
ll euler_phi(ll n){
    ll res=n;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            res=res/i*(i-1);
            for(;n%i==0;n/=i);
        }
    }
    if(n!=1) res=res/n*(n-1);
    return res;
}
ll gcd (ll a, ll b){
    if (b==0) return a;
    return gcd(b, a%b);
}
ll extgcd(ll a, ll b, ll& x, ll&y){
    ll d=a;
    if(b!=0){
        d=extgcd(b, a%b, y, x);
        y-=(a/b)*x;
    }
    else {
        x=1; y=0;
    }
    return d;
}
ll mod_inverse(ll a, ll m){
    ll x,y;
    extgcd(a,m,x,y);
    return (m+x%m)%m;
}
ll mod_pow(ll x, ll n, ll mod){
    if (n==0) return 1;
    ll res=mod_pow(x*x%mod, n/2, mod);
    if (n%2==1) res=res*x%mod;
    return res;
}
ll mul (ll a, ll b,ll m){
    if(a>b) swap(a,b);
    ll ans=0;
    ll res=0;
    while(b>0){
        ll temp=a*(b%10);
        rep(i,0,res){
            temp*=10;
            temp%=m;
        }
        res++;
        ans+=temp;
        ans%=m;
        b/=10;
    }
    return ans;
}
pair<ll, ll> linear_congruence(vector<ll>& A,vector<ll>& B,vector<ll>& M){
    ll x=0, m=1;
    rep(i,0,A.size()){
        ll a=m%M[i], b=((B[i]-x)%M[i]+M[i])%M[i], d=gcd(M[i],a);
        if(b%d!=0) return make_pair(0,-1); //解がない
        if(M[i]>1e15){
            ll t=B[i];
            while(1){
                if(t%m==x){
                    x=t;
                    m*=M[i]/d;
                    break;
                }
                else t+=M[i];
            }
        }
        else if(x>1e15){
            ll t=x;
            while(1){
                if(t%M[i]==B[i]){
                    x=t;
                    m*=M[i]/d;
                    break;
                }
                else t+=m;
            }
        }
        else{
            ll t=mul(b/d,mod_inverse(a/d,M[i]/d),M[i]/d);
            x=x+m*t;
            m*=M[i]/d;
        }
    }
    return make_pair(x%m,m);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int Q;
    cin>>Q;
    while(Q){
        Q--;
        ll A,M;
        cin>>A>>M;
        if(M==1){
            cout <<1<<"\n";
            continue;
        }
        else if(A==0){
            cout <<M<<"\n";
            continue;
        }
        else if(A==1){
            cout <<1<<"\n";
            continue;        }
        else{
            map<ll, ll> a,m;
            a=prime_factor(A);
            m=prime_factor(M);
            vector<ll> C,D,E;
            map<ll,P> modulo;//全てのmodについて記憶　素因数　max指数 mod
            for(auto itr=m.begin(); itr!=m.end();itr++){
                if(a[itr->first]>0){
                    C.pb(1);
                    D.pb(0);
                    E.pb(mod_pow(itr->first,itr->second,1e12));
                    modulo[itr->first]=P(itr->second,mod_pow(itr->first,itr->second,1e12));
                }
                else{
                    ll p=itr->first, e=itr->second;
                    ll s=1;
                    map<ll,ll> prime;
                    prime=prime_factor(mod_pow(p,e,1e18)-1);
                    vector<ll> u,v,w;
                    for(auto ITR=prime.begin(); ITR!=prime.end();ITR++){
                        if(modulo.find(ITR->first)!=modulo.end()){
                            u.pb(1);
                            v.pb(modulo[ITR->first].sc);
                            w.pb(mod_pow(ITR->first,ITR->second,1e18));
                        }
                    }
                    u.pb(1);
                    v.pb(1);
                    w.pb(p);
                    pair<ll,ll> X=linear_congruence(u, v, w);
                    s=(X.first+X.second)%X.second+X.second;
                    ll q=(p-1)*(((s-mod_pow(A%p,s,p))%p+p)%p)+s;
                    rep(i,1,e){
                        q=(p-1)*mod_pow(p,i,2e18)*(((q-mod_pow(A,q,mod_pow(p,i+1,2e18)))/mod_pow(p,i,2e18)%p+p)%p)+q;
                    }
                    for(auto ITR=prime.begin(); ITR!=prime.end();ITR++){
                        if(modulo.find(ITR->first)!=modulo.end()&&modulo[ITR->first].fr<(ITR->second)) modulo[ITR->first]=P(ITR->second,modulo[ITR->first].sc);
                        else if(modulo.find(ITR->first)==modulo.end()) modulo[ITR->first]=P(ITR->second,q%mod_pow(ITR->first,ITR->second,1e18));
                    }
                    modulo[p]=P(e,q%mod_pow(p,e,1e18));
                    C.pb(1);
                    D.pb(q);
                    E.pb((p-1)*mod_pow(p,e,2e18));
                    }
            }
            pair<ll,ll> u=(linear_congruence(C, D, E));
            cout <<(u.first+u.second)%u.second+u.second<<"\n";
        }
    }
}