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>
#define int long long
inline int sqr(int a,int m){return a*a%m;}
int pow(int a,int n,int m)
{
	if(n<1)return 1;
	if(n&1)return sqr(pow(a,n>>1,m),m)*a%m;
	return sqr(pow(a,n>>1,m),m);
}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
void gcd(int x,int y,int &a,int &b)
{
	if(!y){a=1;b=0;return;}
	gcd(y,x%y,b,a);b-=x/y*a;
}
int solve(int a,int m)
{
	if(m==1)return 1;
	int phi=m,k=m;
	for(int i=2;i*i<=m;i++)
		if(k%i==0)
		{
			phi=phi/i*(i-1);
			while(k%i==0)k/=i;
		}
	if(k>1)phi=phi/k*(k-1);
	int g=gcd(m,phi),y=solve(a,g),o=((pow(a,y,m)-y)%m+m)%m,p,q;
	gcd(phi,m,p,q);
	p=(p+m)%m*o/g%m;
	int res=(phi*p+y)%(m*phi);
	if(!res)res=m*phi;
	return res;
}
int q,a,m;
signed main()
{
	scanf("%lld",&q);
	while(q--)
	{
		scanf("%lld%lld",&a,&m);
		printf("%lld\n",solve(a,m));
	}
	return 0;
}