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<bits/stdc++.h>
using namespace std;
long long gcd(long long x,long long y){
	if(x%y==0)return y;
	return gcd(y,x%y);
}
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 d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
long long phi(long long x){
	int ans=1;
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			ans*=(i-1);
			x/=i;
			while(x%i==0)x/=i,ans*=i;
		}
	}
	if(x!=1)ans*=(x-1);
	return ans;
}
long long power(long long x,long long k,long long P){
	long long ans=1;
	while(k){
		if(k&1)(ans*=x)%=P;
		(x*=x)%=P;
		k>>=1;
	}
	return ans;
}
long long solve(long long a,long long m){
	if(m==1)return 1;
	long long M=phi(m);
	long long d=gcd(M,m);
	long long t=solve(a,d);
	long long At=power(a,t,m);
	long long x,y;
	exgcd(M/d,m/d,x,y);
	__int128 A=(At-t%M)/d*x;
	__int128 ans=(__int128)t%M+A*M;
	ans%=m/d*M;
	ans+=m/d*M;
	ans%=m/d*M; 
	ans+=m/d*M; 
//	printf("%lld\n",ans);
	return ans;
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		long long x,m;
		scanf("%lld%lld",&x,&m);
		long long ans=solve(x,m);
		printf("%lld\n",ans);
	}
}