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>

typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


ll pw(ll a, ll b, ll MOD) {
	ll ans = 1;
	a %= MOD;
	while (b) {
		while (!(b & 1))
			a = (a * a) % MOD, b >>= 1;
		ans = (ans * a) % MOD, --b;
	}
	return ans;
}


ll getphi(ll m) {
	ll ans = 1;
	for (ll i = 2; i * i <= m; ++i) {
		if (m % i != 0)
			continue;
		ans *= (i - 1);
		m /= i;
		while (m % i == 0)
			m /= i, ans *= i;
	}
	if (m != 1)
		ans *= (m - 1);
	return ans;
}

ll gcd(ll a, ll b) {
	while (b) {
		ll q = a % b;
		a = b;
		b = q;
	}
	return a;
}

void egcd(ll a, ll b, ll &x, ll &y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return;
	}
	ll x1 = 0, y1 = 0;
	egcd(b, a % b, x1, y1);
	x = y1;
	y = x1 - (a / b) * y1;
}

ll get(ll a, ll m) {
	if (m == 1) {
		return 100;
	}
	ll phi = getphi(m);
	ll d = gcd(phi, m);
	ll x = get(a, d);
	ll go = pw(a, x, m) - x;
	go %= m;
	if (go < 0)
		go += m;
	ll a1 = 0, b = 0;
	egcd(m, phi, a1, b);
	b *= (go / d);
	b %= m;
	if (b < 0)
		b += m;
	x += b * phi;
	if (x - phi * m >= 100)
		x -= phi * m;
	return x;
}

void solve() {
	ll a, m;
	cin >> a >> m;
	ll x = get(a, m);
	assert(pw(a, x, m) == (x % m));
	cout << get(a, m) << "\n";
}

int main() {
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		solve();
	}
	return 0;
}