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>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}

ll power(ll a, ll n, int mo){
	a%=mo;ll res=1;
	while(n){
		if(n&1)res=res*a%mo;a=a*a%mo;n>>=1;
	}
	return res;
}
ll gcd(ll a, ll b){return !b?a:gcd(b,a%b);}
ll getphi(ll n){
	ll res=n;
	for(ll i=2;i*i<=n;i++)if(n%i==0){
		while(n%i==0)n/=i;res=res/i*(i-1);
	}
	if(n>1)res=res/n*(n-1);
	return res;
}
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;
}
ll solve(int a, int m){
	if(m==1)return 1e9+7;
	ll phi=getphi(m),g=gcd(m,phi);
	ll k=solve(a,g);
	ll f=(power(a,k,m)-k)/g,e,d;
	exgcd(phi/g,m/g,e,d);e=(e*f%(m/g)+m/g)%(m/g);
	return k+e*phi;
}
int main() {
	int T;read(T);while(T--){
		int a,m;read(a);read(m);
		ll res=solve(a,m);
		printf("%lld\n",res);
		assert((power(a,res,m)-res)%m==0);
	}
	return 0;
}