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:
/* Tenka1 Programmer Contest F
   欧拉定理:若a,n互质,则a^phi(n)=1(mod n).
   于是,若a,n互质,则a^m=a^(m mod phi(n)) (mod n). 
   更多地,有指数循环节,
   当m>=phi(n)的时候,有a^m=a^(m%phi(n)+phi(n)) (mod n)
   从而可以降幂求解.
   -------------------------------------------------------
   考虑利用这样的性质递归下去求解,
   已知a^k=k (mod m),则a^(k mod phi(m)+phi(m))=k (mod m)
   找到一个t满足t=k(mod phi(m))且t>=phi(m),
   则有a^t=a^k (mod m).
   由a^t=a^k(mod m),t=k(mod phi(m)),a^k=k (mod m)
   则a^t=t (mod gcd(m,phi(m))).
   这样问题就被规约到了gcd(m,phi(m))规模上,共有logM层.
   现在通过迭代,如果已经找到了一个符合条件的t,考虑如何倒推回k, 
   则x=a^t (mod m)  x=t (mod phi(m))这样的不定方程的解x符合条件,
   于是可化为: x-k*m=(a^t)%m
               x-l*phi(m)=t%phi(m)
    即:k*m+(a^t)%m=l*phi(m)+t%phi(m)
	   k*m-l*phi(m)=t%phi(m)-(a^t)%m
	   可以用exgcd解出一组合法的k,l,
	   由k,l是合法解,
	   显然k+p*phi(m),l+p*m也是一组合法解,
	找到符合条件的最小合法解返回即可. 
	然后通过x=(a^t)%m+k*m得到合法的x,
	x就是一个合法的答案.
*/ 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll qmul(ll a,ll b,ll p)
{ll res=1,tp=a;
while (b)
{if (b&1ll) {res*=tp;res%=p;}
tp*=tp;tp%=p;b>>=1ll;
}
return res;
}
inline ll phi(ll n)
{ll ret=n;
for (ll i=2;i*i<=n;i++)
{if (n%i==0)
{while (n%i==0) n/=i;
ret=ret/i*(i-1);
}
}
if (n>1) ret=ret/n*(n-1);
return ret;
}
ll gcd(ll a,ll b)
{if (b==0) return a;
return gcd(b,a%b);
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{if (b==0) {x=1;y=0;return a;}
ll g=exgcd(b,a%b,y,x);
y-=a/b*x;
return g;
}
ll solve(ll a,ll m)
{if (m==1) return 1ll;
ll t,at,pm=phi(m),d=gcd(m,pm),k,l;
t=solve(a,d);
at=qmul(a,t,m);
exgcd(m,pm,k,l);
k*=(((t%pm)-at)/d);k%=pm;
if (k<0) k+=pm;
return (k+pm)*m+at;
}
int main (){
	int test;
	ll a,m;
	scanf ("%d",&test);
	while (test--)
	{scanf ("%lld%lld",&a,&m);
	printf ("%lld\n",solve(a,m));
	}
	return 0;
}