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 <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <string>
#include <set>
#include <map>

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

ll gcd(ll x,ll y)
{
	if(x==0) return y;
	return gcd(y%x,x);
}
ll euler(ll N)
{
	ll ret=N;
	for(ll i=2;i*i<=N;i++)
	{
		if(N%i==0)
		{
			ret/=i;
			ret*=i-1;
			while(N%i==0) N/=i;
		}
	}
	if(N>1)
	{
		ret/=N;
		ret*=N-1;
	}
	return ret;
}
ll mpow(ll m,ll t,ll mod)
{
	if(t==0) return 1;
	ll ret=mpow(m,t/2,mod);
	ret=ret*ret%mod;
	if(t%2==1) ret=ret*(m%mod)%mod;
	return ret;
}
ll solve(ll A,ll m1,ll m2)
{
	if(m2==1) return 1;
	ll pm2=euler(m2);
	ll g=gcd(pm2,m2);
	ll ret=solve(A,m1,g);
	ll vt=mpow(A,m1*(ret%pm2)%pm2,m2)-m1*(ret%m2)%m2;
	if(vt<0) vt+=m2;
	ll z=m1*pm2%m2;
	z/=g,vt/=g;
	ll L=vt*mpow(z,pm2-1,m2)%m2;
	//printf("%lld %lld\n",m1,m2);
	//printf("%lld %lld : %lld %lld %lld\n",A,ret,vt,z,L);
	
	
	ll ans=ret+L*pm2;
	ans%=pm2*m2;
	
	//printf("%lld %lld %lld : %lld %lld\n",A,m1,m2,mpow(A,ans,m2),ans%m2);
	return ans;
}
int main()
{
	int Q;
	scanf("%d",&Q);
	while(Q--)
	{
		ll A,M;
		scanf("%lld %lld",&A,&M);
		if(A==0)
		{
			printf("%lld\n",M);
			continue;
		}
		ll now=M;
		ll m1=1,m2=1;
		for(ll i=2;i*i<=now;i++)
		{
			while(now%i==0)
			{
				if(A%i==0) m1*=i;
				else m2*=i;
				now/=i;
			}
		}
		if(now>1)
		{
			if(A%now==0) m1*=now;
			else m2*=now;
		}
		ll mod=euler(M)*M;
		ll ret=solve(A,m1,m2)*m1%mod;
		if(ret==0) ret+=mod;
		printf("%lld\n",ret);
		//printf("%lld %lld\n",mpow(A,ret,M),ret%M);
	}
	return 0;
}