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 SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

// >= 91
ll A, M;
ll getPhi(ll m) {
	ll res = 1;
	for(int i=2; i*i<=m; i++) {
		if(m%i == 0) {
			m /= i; res *= i-1;
			while(m%i == 0) m /= i, res *= i;
		}
	}
	if(m != 1) res *= m-1;
	return res;
}
ll getMul(ll a, ll b, ll m) {
	ll r = 0, p = a;
	while(b) {
		if(b%2) r = (r + p) % m;
		p = (p + p) % m;
		b >>= 1;
	}
	return r;
}
ll getPow(ll a, ll b, ll m) {
	ll r = 1, p = a;
	while(b) {
		if(b%2) r = getMul(r, p, m);
		p = getMul(p, p, m);
		b >>= 1;
	}
	return r;
}
ll ee(ll a, ll b, ll &s, ll &t) {
	if(b == 0) {
		s = 1; t = 0;
		return a;
	}
	ll ss, tt, g = ee(b, a%b, ss, tt);
	ll q = a / b;
	s = tt;
	t = ss - q * tt;
	return g;
}
ll toPlus(ll a, ll m) {
	a %= m; if(a < 0) a += m;
	return a;
}
ll getCRT(ll a, ll c, ll b, ll d) {
	//printf("%lld %lld %lld %lld\n", a, c, b, d);
	ll s, t;
	ll g = ee(c, d, s, t);
	s = toPlus(s, d), t = toPlus(t, c);
	if(g > 1) {
		return getCRT(a/g, c/g, b/g, d/g) * g + a%g;
	}
	ll av = getMul(getMul(a, d, c*d), t, c*d);
	ll bv = getMul(getMul(b, c, c*d), s, c*d);
	ll k = (av + bv) % (c*d);
	if(k == 0) k = c*d;
	return k;
}
ll getAns(ll a, ll m) {
	ll pm = getPhi(m);
	if(m < 91) {
		for(int i=1; i<=pm*m; i++) if(getPow(a, i, m) == (i % m)) return i;
		return -1;
	}
	ll c, d;
	ll g = ee(pm, m, c, d);
	ll y = getAns(a, g);
	if(y == -1) return -1;
	ll Ay = getPow(a, y, m);
	ll yg = y / g, Ayg = Ay / g;

	//printf("%lld %lld - > %lld [%lld %lld]\n", a, g, y, c, d);
	ll x = getCRT(getPow(a, y, m), m, y, pm);
	//printf("[%lld %lld] (%lld) %lld %lld\n", a, m, x, getPow(a, x, m), x % m);
	return x;
}
int main() {
	int T; cin >> T;
	for(int tc=1; tc<=T; tc++) {
		scanf("%lld%lld", &A, &M);
		//printf("%lld\n", getAns(A, M));
		ll v = getAns(A, M);
		printf("%lld\n", v);
		//if(v > 0) printf("%lld %lld\n", getPow(A, v, M), v % M);
	}
	return 0;
}