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<cassert>

typedef long long ll;
typedef __int128 u128;

ll gcd(ll a,ll b)
{
	return !b?a:gcd(b,a%b);
}

int fpow(int a,ll b,int c)
{
	ll w=1,o=a;
	while(b) {
		if(b&1) w=w*o%c;
		o=o*o%c;
		b>>=1;
	}
	return w;
}

int Phi(int n)
{
	int r=n;
	for(int i=2; i*i<=n; i++)
		if(n%i==0)
		{
			r=r/i*(i-1);
			while(n%i==0)n/=i;
		}
	if(n>1)r=r/n*(n-1);
	return r;
}

ll exgcd(ll a,ll b,ll&x,ll&y)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	ll c=exgcd(b,a%b,x,y);
	ll t=x;
	x=y;
	y=t-a/b*y;
	return c;
}

ll Inv(ll a,ll b)
{
	ll x,y;
	exgcd(a,b,x,y);
	return(x+b)%b;
}

ll now,M;

void excrt(ll a,ll b)
{
	ll c=((a-now)%b+b)%b;
	ll x,y;
	ll d=exgcd(M,b,x,y);
	assert(c%d==0);
	c/=d;
	b/=d;
	x=(x%b+b)%b;
	x=(u128)x*c%b;
	now+=x*M;
	M*=b;
}

int T,n,m;

ll solve(int d)
{
	if(d==1)
		return 1;
	int pd=Phi(d);
	ll y=solve(gcd(d,pd));
	now=y%pd;
	M=pd;
	excrt(fpow(n,y,d),d);
	return !now?M:now;
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		printf("%lld\n",solve(m));
	}
	return 0;
}