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;
#define ll long long
ll power(ll x,ll k,ll mo)
{
	ll cnt=1;
	while(k){
		if(k&1) cnt=cnt*x%mo;
		x=x*x%mo;
		k>>=1;
	}
	return cnt;
}
ll phi(ll n)
{
	ll res=n,t=n;
	for(ll i=2;i*i<=t;i++)
		if(t%i==0){
			res-=res/i;
			while(t%i==0) t/=i;
		}
	if(t>1) res-=res/t;
	return res;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0) {x=1;y=0; return a;}
	ll g;
	g=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return g;
}
ll solve(ll A,ll M)
{
	if(M==1) return 1;
	ll phiM,At,t,x,y,g;
	phiM=phi(M);
	g=gcd(M,phiM);
	t=solve(A,g);
	At=power(A,t,M);
	
	exgcd(M/g,phiM/g,x,y);
	
	x=x*(((t-At)%phiM+phiM)%phiM)/g;
	x=((x%(phiM/g)+phiM/g)%(phiM/g)+phiM/g);
	return x*M+At;
}
int main()
{
	int Q;
	cin>>Q;
	while(Q--){
		ll A,M;
		cin>>A>>M;
		cout<<solve(A,M)<<endl;
	}
}