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>
long long modpow(long long a,long long b,long long p)
{
	long long ret=1;
	for(;b>0;b>>=1,a=(a*a)%p)
		if(b&1)
			ret=(ret*a)%p;
	return ret;
}
long long phi(long long n)
{
	long long res=n,t=n;
	for(long long 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;
}
long long gcd(long long a,long long b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if(b==0)
    {x=1;y=0;return a;}
    long long g;
    g=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return g;
}
long long solve(long long A,long long M)
{
	if(M<=500)
	{
		long long s=A;
		for(long long i=1;;i++)
		{
			if(s==i%M)
				return i;
			s=(s*A)%M;
		}
	}
	long long pM,At,d,t,x,y;
	pM=phi(M);
	d=gcd(M,pM);
	t=solve(A,d);
	At=modpow(A,t,M);
	exgcd(M/d,pM/d,x,y);
	x=x*(((t-At)%pM+pM)%pM)/d;
	x=((x%(pM/d))+pM/d)%(pM/d)+pM/d;
	return x*M+At;
}
int main()
{
	int Q;
	long long A,M;
	scanf("%d",&Q);
	while(Q--)
	{
		scanf("%lld%lld",&A,&M);
		printf("%lld\n",solve(A,M));
	}
	return 0;
}