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>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000

#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
ll gcd(ll a,ll b){
	if(a<b)swap(a,b);
	if(b==0) return a;
	else return gcd(b,a%b);
}
ll extgcd(ll a,ll b,ll &x,ll &y){
	ll g = a; x = 1; y = 0;
	if(b != 0) g = extgcd(b,a%b,y,x),y-=(a/b)*x;
	return g;
}
ll AxB(ll A,ll B,ll C){
	//minimum non-negaitive x such that Ax godo b (mod C)
	if(B%gcd(A,C) != 0) return -1;
	ll x,y;
	extgcd(A,C,x,y);
	x = x*B/gcd(A,C)%(C/gcd(A,C));
	ll f = C/gcd(A,C);
	if(x > 0){
		x %= abs(f);
	}
	else{
		x = (x%abs(f)+abs(f))%abs(f);
	}
	return x;
}
ll modpow(ll x,ll n,ll mod)
{
	ll res=1;
	while(n>0)
	{
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
int q;
ll a,m;
vector<ll>A;
ll rec(ll a,ll m){
	if(a == 0) return m*100LL;
	if(a == 1) return m*100LL+1LL;
	if(m == 1) return m*100LL;
	//a>=2 && m>=2
	//例外
	//cycを求める
	ll M = m;
	rep(i,A.size()){
		while(M%A[i] == 0) M/=A[i];
	}
	ll MM = M;
	for(ll x=2;x*x<=M;x++){
		if(M%x == 0){
			MM = (MM/x) * (x-1);
			while(M%x == 0) M/=x;
		}
	}
	if(M != 1) MM = (MM/M) * (M-1);
	ll cur = 1;
	ll ok = MM/gcd(MM,m)*m;
	rep(x,100){
		if(cur%m == x%m){
		    if(ok>=100) return x+ok;
		    else return x+ok*100LL;
		}
		cur = cur*a%m;
	}
	//cyc = MM
	ll ans = rec(a,MM);
	if(ans == -1) return -1;
	//a^ansとansがmod cycで合同
	ll dif = modpow(a,ans,m)-ans;
	dif = (dif%m+m)%m;
	//difはcyc*?1-m*?2と思える
	//dif+m*?をcycの倍数にしたい、これは上より必ず可能
	//mxと-difがmod cycで合同
	ll q = AxB(m,(MM-dif%MM)%MM,MM);
	if(q<0) return -1;
	ans = (ans+dif+m*q%ok)%ok;
	if(ans<100){
	    if(ok>=100) ans+=ok;
	    else ans+=ok*100LL;
	}
	return ans;
}
int main(){
	cin>>q;
	rep(e,q){
		cin>>a>>m;
		A.clear();
		ll b = a;
		for(ll i=2;i*i<=b;i++){
			if(b%i==0){
				A.pb(i);
				while(b%i==0) b/=i;
			}
		}
		if(b != 1) A.pb(b);
		ll K = rec(a,m);
		if(K >= 0){
		    ll Q = modpow(a,K,m);
		    ll R = K%m;
		    assert(Q == R);
		}
		cout<<K<<endl;
	}
}