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>
#include<algorithm>
using namespace std;
int Q;
long long Pow(long long a, long long b, long long Mod){
    long long r = 1;
    while(b){
        if(b&1)r=r*a%Mod;
        a=a*a%Mod;b>>=1;
    }
    return r;
}
int Phi(int a){
    int i, r = a;
    for(i=2;i*i<=a;i++){
        if(a%i==0){
            r = r/i*(i-1);
            while(a%i==0)a/=i;
        }
    }
    if(a!=1){
        r=r/a*(a-1);
    }
    return r;
}
int gcd(int a, int b){
    return b?gcd(b,a%b):a;
}
long long Calc(int a, int m){
    int i;
  //  printf("%d %d\n",a,m);
    if(m <= 500){
        int s = 1;
        for(i=1;;i++){
            s = 1ll*s*a%m;
            if(s==i%m)return i;
        }
        return -1;
    }
    int p = Phi(m);
    int G = gcd(m,p);
    long long r = Calc(a, G);
    if(r == -1)return -1;
//    printf("%lld %lld\n",r%G, Pow(a,r,G));
//    printf("%lld\n",r);
    long long t = (Pow(a, r, m) + m - r)%m;
//    printf("%lld\n",Pow(a,r,m));
//    printf("%d %lld\n",G,t);
    int p2 = p/G, m2 = m/G;
    long long t2 = t/G;
    int pm = Phi(m2);
    long long ttt = 1ll * Pow(p2, pm - 1, m2) * t2 % m2;
    long long res = ttt * p + r;
    //printf("%lld %lld\n",Pow(a,res,m), res%m);
    return res;
}
int main(){
    int i;
    int a, m;
    scanf("%d",&Q);
    while(Q--){
        scanf("%d%d",&a,&m);
        printf("%lld\n",Calc(a,m));
    }
}