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<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
#include<cassert>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=500000004;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
long long gcd(long long a,long long b){
	while(a){
		b%=a;swap(a,b);
	}return b;
}
long long p(long long a){
	long long ret=a;
	long long b=a;
	for(int i=2;i*i<=a;i++){
		if(b%i==0){
			ret=ret/i*(i-1);
			while(b%i==0)b/=i;
		}
	}
	if(b>1){
		ret=ret/b*(b-1);
	}
	return ret;
}
long long gojo(long long a,long long b,long long &x,long long &y){
	if(b){long long g=gojo(b,a%b,y,x);y-=(a/b)*x;return g;}
	x=1;y=0;return a;
}
long long po(long long a,long long b,long long m){
	long long ret=1%m;
	while(b){
		if(b%2)ret=ret*a%m;
		a=a*a%m;
		b/=2;
	}
	return ret;
}
pair<long long,long long> solve(long long a,long long b){
	if(b==1)return make_pair(0LL,0LL);
	long long c=p(b);
	pair<long long,long long>ret=solve(a,c);
	return make_pair(po(a,ret.first+50*c,b),ret.first);
}
int main(){
	int T;scanf("%d",&T);
	while(T--){
		int a,b;scanf("%d%d",&a,&b);
		if(a==0){
			printf("%d\n",b);continue;
		}
		if(a==1){
			printf("%d\n",1);continue;
		}
		pair<long long,long long> ret=solve(a,b);
	//	printf("%lld %lld, %lld %lld\n",b,ret.first,p(b),ret.second);
		long long g=gcd(b,p(b));
		long long sm=b;
		long long tm=p(b);
		long long x,y;
		gojo(sm,tm,x,y);
		long long v=sm*tm;
		long long nm=sm*tm/g;
		long long q=ret.first+x*(ret.second-ret.first)/g%tm*sm;
		q%=v;q+=v;q%=v;
		//printf("%lld\n",q);
		while(q<50)q+=v;
		printf("%lld\n",q);
	}
}