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;

typedef long long ll;

ll pow_mod(ll x,ll k,int MOD) {
  ll ans=1;
  while (k) {
  	if (k&1) ans=ans*x%MOD;
  	x=x*x%MOD;
  	k>>=1;
  }
  return ans;
}

inline int gcd(int x,int y) {
  return (x%y==0)?y:gcd(y,x%y);
}

inline ll lcm(int x,int y) {
  return (ll)x/gcd(x,y)*y;
}

int getphi(int n) {
  int s=n,t=n;
  for(int i=2;i*i<=t;i++)
    if (n%i==0) {
    	s=s/i*(i-1);
    	while (n%i==0) n/=i;
	}
  if (n>1) s=s/n*(n-1);
  return s;
}

void exgcd(ll a,ll b,ll &x,ll &y) {
  if (!b) {
  	x=1;y=0;
  }
  else {
  	exgcd(b,a%b,y,x);
  	y-=(a/b)*x;
  }
}

ll getinv(ll x,ll MOD) {
  ll t1,t2;
  exgcd(x,MOD,t1,t2);
  return (t1%MOD+MOD)%MOD;
}

ll excrt(int n,int m,ll x,ll y) {
  ll v=lcm(n,m);
  int d=gcd(n,m);
  n/=d;m/=d;
  ll ans=((y-x)/d%m+m)*getinv(n,m)%m;
  return (ans*n*d+x)%v;
}

ll solve(int a,int n) {
  if (n==1) return 1;
  int m=getphi(n);
  ll x=solve(a,gcd(n,m)),y=pow_mod(a,x,n);
  x%=m;
  ll ans=excrt(m,n,x,y);
  if (ans<=m) ans+=lcm(n,m);
  return ans;
}

int main() {
  int cases;
  scanf("%d",&cases);
  for(;cases;cases--) {
  	int x,y;
  	scanf("%d%d",&x,&y);
  	printf("%lld\n",solve(x,y));
  }
  return 0;
}