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,l,r) for (int i=l,i##end=r;i<=i##end;++i)
#define per(i,r,l) for (int i=r,i##end=l;i>=i##end;--i)
#define rep0(i,r) for (int i=0,i##end=r;i<i##end;++i)
#define ll long long
using namespace std;
ll M;
ll mul(ll x,ll y,ll m){
    ll s=0; for (;y;y>>=1,x=(x+x)%m) if (y&1) s=(s+x)%m;
    return s;
}
ll fpw(ll x,ll y,ll m){
    ll s=1; x%=m;
    for (;y;y>>=1,x=x*x%m) if (y&1) s=s*x%m;
    return s;
}
ll gcd(ll x,ll y){ return y==0?x:gcd(y,x%y); }
void exgcd(ll a,ll b,ll &x,ll &y){
    if (b==0){ x=1,y=0; return; }
    exgcd(b,a%b,y,x); y-=a/b*x;
}
ll phi(ll n){
    ll s=1;
    rep(i,2,sqrt(n))
        if (n%i==0){
            s*=i-1,n/=i; while (n%i==0) s*=i,n/=i;
            if (n==1) break;
        }
    return s*(n==1?1:n-1);
}
ll solve(ll a,ll m){
    if (m==1) return M;
    ll p=phi(m),g=gcd(m,p),_y=solve(a,g);
    ll pw=fpw(a,_y,m),c=_y%p-pw;
    //ans=m*x+pw=p*y+_y m*x-p*y=pw-_y
    //m*x-p*y=c
    ll x1,y1; exgcd(m,p,x1,y1);
    x1=(x1%(p/g)+(p/g))%(p/g)*(c/g);
    ll d=m*p/g; x1=(x1%d+d)%d;
    ll ans=(mul(x1,m,d)+pw)%d;
    if (ans<M) ans+=(M-ans+d-1)/d*d;
    while (ans<M) ans+=d;
    return ans;
}
int main(){
    int q; cin>>q;
    while (q--){
        ll a,m; cin>>a>>m; M=phi(m);
        ll s=solve(a,m); cout<<s<<endl;
    }
    return 0;
}
/*
1
123456789 987654321
*/