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;
#define ll long long

ll t,n,m;

inline ll rd()
{
	ll x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

inline void print(ll x)
{
	static char s[233];
	if (!x) { putchar('0');putchar('\n');return; }
	int tot=0;
	for (;x;x/=10) s[++tot]=x%10+'0';
	for (;tot;tot--) putchar(s[tot]);
	putchar('\n');
}

inline ll gcd(ll x,ll y) { return (!y)?x:gcd(y,x%y); }

inline void ex_gcd(ll a,ll b,ll &x,ll &y)
{
	if (!b) { x=1;y=0;return; }
	ex_gcd(b,a%b,x,y);
	ll hh=x;x=y;y=hh-(a/b)*y;
}

inline ll ksm(ll x,ll y,const ll &mod) { ll res=1;for (;y;y>>=1,x=x*x%mod) if (y&1) res=res*x%mod;return res; }

inline ll calc(ll n)
{
	ll res=1;
	for (ll i=2;i*i<=n;i++) if (n%i==0)
	{
		res*=(i-1);n/=i;
		while (n%i==0) n/=i,res*=i;
	}
	if (n>1) res*=(n-1);
	return res;
}

inline ll gao(ll n,ll m,ll lim)
{
	if (m==1) return lim;
	ll phi=calc(m),d=gcd(m,phi),hh=gao(n%d,d,phi);
	ll x,y;
	ex_gcd(phi,m,x,y);
	x=(x%m+m)%m;
	ll hhh=ksm(n,hh,m)-hh,res;
	ll now=m*phi/d;
	if (hhh==0) res=hh;
	else res=(hh+(__int128)x*phi*(hhh/d))%now;
	res+=(lim-res)/now*now;
	while (res<lim) res+=now;
	while (res-now>=lim) res-=now;
	return res;
}

int main()
{
	t=rd();
	while (t--)
	{
		n=rd();m=rd();n%=m;
		ll ans=gao(n,m,calc(m));
		print(ans);
	}
	return 0;
}