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<stdio.h>
#include<assert.h>
#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<algorithm>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int MX = 200005;
const int MM = 1000000007;

ll gcd(ll a, ll b){
	return b ? gcd(b, a%b) : a;
}

ll pw(ll a, ll b, ll M){
	ll r = 1;
	while(b){
		if( b&1 ) r = r*a % M;
		a = a*a % M; b /= 2;
	} return r;
}

pll ex_gcd(ll a, ll b){
	if( b == 0 ) return pll(1, 0);
	else{
		pll t = ex_gcd(b, a%b);
		// b * t.first + (a - b*a/b) * t.second
		return pll(t.second, t.first - a/b*t.second);
	}
}

ll get_answer(ll a, ll b, ll c, ll d){
	ll g = gcd(b, d);
	pll t = ex_gcd(b, d);
	ll x = ((__int128) (c-a)/g * t.first * b + a) % (b*d/g);
	assert((c-a)%g == 0);
	if( x < 32 ) x += b*d/g;
	return x;
}

ll inv(ll A, ll B){
	assert(gcd(A, B) == 1);
	pll t = ex_gcd(A, B);
	return (t.first%B + B) % B;
}

ll P(ll X){
	ll r = 1;
	for(int i = 2; i*i <= X; i++){
		if( X%i == 0 ){
			X /= i, r *= (i-1);
		}
		while( X%i == 0 ){
			X /= i, r *= i;
		}
	}
	if( X != 1 ) r *= (X-1);
	return r;
}

ll O = 1;
ll F1(int A, int M){
	if( A == 0 ) return M*(30/M+1);
	ll B = A, N = M;
	if( gcd(A, M) != 1 ){
		while(gcd(A, N) != 1){
			O *= gcd(A, N); N /= gcd(A, N);
		}
		ll x = F1(pw(A, O, N), N) * O;
		return x;
	}
	ll Pi = P(M), G = gcd(Pi, M);
	ll xi = F1(A%G, G);
	
	ll x = get_answer(pw(A, xi, M) * inv(O, M) % M, M, xi, Pi);
	return x;
}

void solve(){
	int A, M;
	scanf("%d%d", &A, &M);
	O = 1;
	ll p = F1(A, M);
	printf("%lld\n", p);
}

int main()
{
	int Q;
	scanf("%d", &Q);
	for(int i = 1; i <= Q; i++) solve();
}