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 <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>

using namespace std;
typedef long long int ll;

ll gcd(ll a, ll b){
	if(b==0) return a;
	return gcd(b, a%b);
}

ll extgcd(ll a, ll b, ll& x, ll& y, ll k){
	ll d=a;
	if(b!=0){
		d=extgcd(b, a%b, y, x, k);
		y-=(a/b)*x;
	}else{
		x=k/a, y=0;
	}
	return d;
}

long long int powmod(long long int a, long long int k, long long int m){ //0<=a<=1e9, 0<k<=1e18, 0<m<=1e9
	if(a==0){
		return 0;
	}
	long long int apow[60], c[60];
	for(int i=0; i<60; i++){
		if(i==0){
			apow[i]=a;
			c[i]=1;
		}else{
			apow[i]=apow[i-1]*apow[i-1]%m;
			c[i]=c[i-1]*2;
		}
	}
	long long int ans=1;
	for(int i=59; i>=0; i--){
		if(k>=c[i]){
			ans=ans*apow[i]%m;
		}
		k=k%c[i];
	}
	return ans;
}

long long int eulerphi(long long int n){
	if(n==1) return 1;
	long long int res=n;
	for(long long int i=2; i*i<=n; i++){
		if(n%i==0){
			res=res/i*(i-1);
			while(n%i==0) n/=i;
		}
	}
	if(n!=1) res=res/n*(n-1);
	return res;
}

ll ans(ll a, ll m){  // ans>=30
	if(a==0) return m;
	if(m==1) return 30;

	ll m1=m, m2=1;
	ll d;
	while((d=gcd(a, m1))>1){
		m1/=d;
		m2*=d;
	}
	ll phi1=eulerphi(m1);
	ll s=ans(a, phi1);
	ll k1=powmod(a, s, m), k2=powmod(a, s, phi1), k;
	ll x, y;
	extgcd(m, phi1, x, y, k2-k1);
	k=m*(x%phi1)+k1;
	while(k<30) k+=(m*phi1);
	return k;
}

int main()
{
	int q;
	scanf("%d", &q);
	for(int i=0; i<q; i++){
		ll a, m, k;
		scanf("%lld %lld", &a, &m);
      k=ans(a, m);
		printf("%lld\n", k);
	}
	return 0;
}