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 bool boolean;

#define ll long long

ll mul(ll a, ll b, ll Mod) {
	return ((__int128) a) * b % Mod;
}

template <typename T>
ll qpow(ll a, T p, ll Mod) {
	ll rt = 1;
	for ( ; p; a = mul(a, a, Mod), p >>= 1) {
		if (p & 1) {
			rt = mul(rt, a, Mod);
		}
	}
	return rt;
}

template <typename T>
void exgcd(T a, T b, T& d, T& x, T& y) {
	if (!b) {
		d = a, x = 1, y = 0;
	} else {
		exgcd(b, a % b, d, y, x);
		y -= (a / b) * x;
	}
}
template <typename T>
T inv(T a, T Mod) {
	T d, x, y;
	exgcd(a, Mod, d, x, y);
	assert(d == 1);
	return (x < 0) ? (x + Mod) : x;
}

boolean excrt(ll a0, ll m0, ll a1, ll m1, ll& a, ll& m) {
	// a0 + k_0 m_0 = a_1 + k_1 m_1
	// x m_0 + (-y) m_1 = a_1 - a_0
	ll d, x, y, da = a1 - a0;
	exgcd(m0, m1, d, x, y);
	if (da % d)
		return false;
	ll k0 = mul(x, da / d, m1 / d);
	m = m0 / d * m1;
	a = a0 + k0 * m0;
	(a < 0) && (a += m);
	return true;
}

#define pii pair<int, int>

vector<pii> factorize(int n) {
	vector<pii> rt;
	for (int i = 2; i * i <= n; i++) {
		if (!(n % i)) {
			int t = 0;
			while (!(n % i))
				t++, n /= i;
			rt.emplace_back(i, t);
		}
	}
	if (n > 1) {
		rt.emplace_back(n, 1);
	}
	return rt;
}

int T;
int a, m;
vector<ll> ms;
vector<ll> as;

int x;

void solve(int a, int p, int r) {
	if (!(a % p)) {
		int M = 1;
		for (int i = 0; i < r; i++, M *= p);
		ms.push_back(M);
		as.push_back(0);
		return;
	}
	ll m0 = p - 1, m1 = p, a0 = x % m0, a1;
	for (int i = 1; i <= r; i++) {
		a1 = qpow(a, a0, m1);
		assert(excrt(a0, m0, a1, m1, a0, m0));
		m1 *= p;
	}
	ms.push_back(m0);
	as.push_back(a0);
}

ll solve(int _a, vector<pii>& fac) {
	ms.clear();
	as.clear();
	for (auto x : fac) {
		solve(_a, x.first, x.second);	
	}
	ll a = 0, m = 1;
	int t = ms.size();
	for (int i = 0; i < t; i++) {
		if (!excrt(a, m, as[i], ms[i], a, m)) {
			return -1;
		}
	}
	while (a < 40)
		a += m;
	return a;
}

int	myrand() {
	const unsigned msk = (1u << 30) - 1; 
	return ((((unsigned) rand()) << 15) ^ rand()) & msk;
}

int main() {
	srand((unsigned) time (NULL));
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &a, &m);
		vector<pii> fac = factorize(m);
		int prod = 1;
		for (auto x : fac)
			prod *= (x.first - 1);
		ll ans = -1;
		while (ans == -1) {
			x = myrand() % prod;
			ans = solve(a, fac);
		}
//		cerr << x << '\n';
//		cerr << qpow(a, ans, m) << " " << ans % m << '\n';
		printf("%lld\n", ans);
	}
	return 0;
}