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 <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int Q;
i64 A[110], M[110];

i64 modpow(i64 a, i64 p, i64 M)
{
	if (p == 0) return 1 % M;
	i64 tmp = modpow(a, p / 2, M);
	tmp = tmp * tmp % M;
	if (p % 2 == 1) tmp = tmp * a % M;
	return tmp;
}
i64 gcd(i64 a, i64 b)
{
	return b == 0 ? a : gcd(b, a % b);
}

i64 solve(i64 a, i64 m)
{
	if (a == 0) {
		return m;
	}
	a %= m;

	if (gcd(a, m) != 1) {
		i64 lf = 1;
		for (int i = 0; i < 32; ++i) {
			if (lf % m == i % m) {
				return i;
			}
			lf = lf * a % m;
		}

		i64 g = gcd(a, m);
		i64 ad = a / g, md = m / g;
		i64 h = g;

		for (;;) {
			i64 aux = gcd(g, md);
			if (aux == 1) break;
			h *= aux;
			md /= aux;
		}

		return solve(modpow(a, h, m), md) * h;
	}
}

i64 euler(int a)
{
	int ret = 1;
	for (int i = 2; i * i <= a; ++i) {
		if (a % i == 0) {
			a /= i;
			ret *= i - 1;
			while (a % i == 0) {
				a /= i;
				ret *= i;
			}
		}
	}
	if (a > 1) ret *= a - 1;
	return ret;
}

i64 tower(i64 a, i64 m) {
	if (m == 1) {
		return 0;
	}
	i64 e = euler(m);
	i64 ret = modpow(a, 30 * e + tower(a, e), m);
	//printf("%lld %lld %lld\n", a, m, ret);
	return ret;
}

i64 extgcd(i64 a, i64 b, i64 m)
{
	if (a == 0) return 0;

	i64 g = gcd(a, m);
	if (g != 1) {
		if (b % g != 0) puts("><");
		return extgcd(a / g, b / g, m / g);
	}

	i64 s = m, t = 0;
	while (a != 1) {
		i64 k = s / a;
		i64 s2 = a;
		i64 t2 = b;

		//printf("%lld %lld %lld\n", a, b, m);
		a = s - a * k;
		b = (t + m - b * k % m) % m;
		s = s2;
		t = t2;
	}
	//printf("%lld %lld %lld\n", a, b, m);

	return (m - b) % m;
}

i64 solve2(i64 a, i64 m) {
	if (a == 0) return m;

	i64 p = euler(m);
	i64 mm = tower(a, m);
	i64 mp = tower(a, p);
	//printf("mm:%lld p:%lld mp:%lld\n", mm, p, mp);
	if (mm == 0 && mp == 0) return m * p;

	i64 x = extgcd(m % p, (mm - mp + p) % p, p);
	//printf("%lld\n", x);
	return x * m + mm;
}

int main()
{
	scanf("%d", &Q);
	for (int i = 0; i < Q; ++i) {
		scanf("%lld%lld", A + i, M + i);
		
		i64 ans = solve2(A[i] % M[i], M[i]);
		printf("%lld\n", ans);
		//printf("%lld %lld\n", ans % M[i], modpow(A[i], ans, M[i]));
	}
	return 0;
}