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>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
int Q;
ll A,M;
ll mpw(ll n,ll m,ll md){
	ll ret=1;
	while(m){
		if(m&1){
			ret*=n;
			ret%=md;
		}
		n*=n;
		n%=md;
		m>>=1;
	}
	return ret;
}
ll gcd(ll a,ll b){
	if(b==0) return a;
	return gcd(b,a%b);
}
ll euler(ll x){
	ll ret=x;
	for(ll i=2;i*i<=x;i++){
		if(x%i==0){
			ret/=i;
			ret*=i-1;
			while(x%i==0){
				x/=i;
			}
		}
	}
	if(x!=1){
		ret/=x;
		ret*=x-1;
	}
	return ret;
}
typedef pair<ll,ll> P;
void extgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1;
		y=0;
	}else{
		ll x2,y2;
		extgcd(b,a%b,x2,y2);
		x=y2;
		y=-a/b*y2+x2;
	}
}
ll minv(ll a,ll m){
	//gcd(a,m)=1
	ll x,k;
	extgcd(a,m,x,k);
	x=(x+m)%m;
	return x;
}
P godoshiki(ll a,ll b,ll m){
	//gcd(a,m)|b
	P ret;
	ret.second=m/gcd(a,m);
	ret.first=minv(a/gcd(a,m),ret.second)*(b/gcd(a,m))%ret.second;
	return ret;
}
ll dfs(ll m){
	if(m==1){
		return 100;
	}
	ll eum=euler(m);
	ll y=dfs(gcd(m,eum));
	P p=godoshiki(eum,(mpw(A,y,m)-y+m)%m,m);
	ll x=y+p.first*eum,md=eum/gcd(m,eum)*m;
	x%=md;
	while(x<100)x+=md;
	return x;
}
	
int main(){
	cin>>Q;
	REP(qry,Q){
		cin>>A>>M;
		cout<<dfs(M)<<endl;
	}
}