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<stdio.h>
#include<assert.h>
typedef long long ll;
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
void exgcd(ll a,ll b,ll&x,ll&y){
	if(!b){
		x=1;
		y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
int phi(int n){
	int i,s=n;
	for(i=2;i*i<=n;i++){
		if(n%i==0){
			s=s/i*(i-1);
			while(n%i==0)n/=i;
		}
	}
	if(n>1)s=s/n*(n-1);
	return s;
}
int pow(int a,ll b,int p){
	int s=1;
	while(b){
		if(b&1)s=(ll)s*a%p;
		a=(ll)a*a%p;
		b>>=1;
	}
	return s;
}
ll solve(int a,int m){
	if(m==1)return 1;
	int p,g,ay;
	ll t,x,y;
	p=phi(m);
	g=gcd(m,p);
	t=solve(a,g);
	ay=pow(a,t,m);
	exgcd(p,m,x,y);
	ay-=t%p;
	if(ay<0){
		x=-x;
		ay=-ay;
	}
	x=((ay/g*x%m+m)%m)*p+t%p;
	t=(ll)m/g*p;
	if(x<t)x+=t;
	return x;
}
void work(){
	int a,m;
	scanf("%d%d",&a,&m);
	printf("%lld\n",solve(a,m));
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--)work();
}