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 <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <deque>
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#include <chrono>
#include <random>
#include <time.h>
#include <fstream>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define all(c) begin(c),end(c)
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
void print(vec v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(vecll v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(map<int,int> mp){for(auto e:mp)cout<<e.first<<" "<<e.second<<endl;cout<<endl;}
void print(pll p) {cout<<"("<<p.first<<","<<p.second<<")"<<endl;}
void print(pii p) {cout<<"("<<p.first<<","<<p.second<<")"<<endl;}

template< typename T >
T extgcd(T a, T b, T &x, T &y) {
  T d = a;
  if(b != 0) {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}
template<typename T>
T gcd(T a,T b){
    if(a>b)return gcd(b,a);
    if(a!=0)return gcd(b%a,a);
    else return b;
}
template<typename T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
ll CRT(ll b1,ll m1,ll b2,ll m2){
    ll p,q;
    ll d=extgcd(m1,m2,p,q);
    ll M=m1/d*m2;
    return ((b1+m1*((b2-b1)/d)*p)%M + M)% M;
}
ll modpow(ll x,ll n,ll mod){
    if(n==0)return 1;
    if(n%2)return modpow(x*x%mod,n/2,mod)*x%mod;
    return modpow(x*x%mod,n/2,mod);
}
ll fai(ll m){
    ll res=1;
    for(ll i=2;i*i<=m;i++){
        if(m%i==0){
            ll tmp=1;
            while(m%i==0){
                m/=i; tmp*=i;
            }
            tmp/=i; tmp*=(i-1);
            res=lcm(res,tmp);
        }
    }
    if(m>1)res=lcm(res,m-1);
    return res;
}
vector<ll> prime_factors(ll _x){
    vecll res;
    ll x=_x;
    for(ll i=2;i*i<=x;i++){
        if(x%i==0){
            while(x%i==0)x/=i;
            res.pb(i);
        }
    }
    if(x>1)res.pb(x);
    return res;
}
ll solve(ll a,ll m,ll d){
    vecll p=prime_factors(gcd(a,m));
    for(ll e:p){
        while(m%e==0){
            m/=e; d*=e;
        }
    }
    a%=m;
    // cout<<a<<" "<<m<<" "<<d<<endl;
    if(m==1)return d;
    ll fm=fai(m);
    ll k=solve(a,gcd(m,fm),d);
    ll left=(((modpow(a,k,m)-k)%m)+m)%m;
    ll t,s;
    extgcd(fm,m,t,s);
    t=(t%m+m)%m;
    k=k+fm*(left/gcd(m,fm)%m*t%m);
    ll M=lcm(m,fm);

    ll MM=lcm(M,d);
    extgcd(M,d,t,s);
    t=(t%d+d)%d;
    t*=(-k/gcd(M,d)%d+d)%d; 
    t=(t%d+d)%d;
    // cout<<a<<" "<<m<<" "<<fm<<" "<<d<<" "<<(k + t*M)%(lcm(lcm(m,fm),d))<<endl;
    return (k + t*M)%(lcm(M,d));
}

int main(){
    int q=in();
    while(q--){
        ll a=lin(),m=lin();
        cout<<solve(a,m,1)<<endl;
    }
}