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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 61; i++) {
		if ((b / (1LL << i)) % 2 == 1) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}

long long gcd(long long a, long long b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

long long find_value(long long a, long long b, long long m) {
	if (a == 0) return 1;
	while ((m%a) != 0) {
		long long cnt = 1;
		while (true) {
			long long G = (cnt * m) / a + 1; cnt++;
			if (gcd(G, m) != 1 || (a*G) % m == a) continue;

			a *= G; a %= m; b *= G; b %= m;
			break;
		}
	}
	return b / a;
}

long long period(long long cc) {
	long long r = 1, c = cc; vector<long long>A;
	for (long long i = 2; i*i <= c; i++) {
		if (c%i != 0) continue;
		A.push_back(i);
		while (c%i == 0) c /= i;
	}
	if (c >= 2) A.push_back(c);

	for (int i = 0; i < A.size(); i++) {
		long long cx = cc, t = A[i] - 1;
		while (cx%A[i] == 0) { if (cx != cc) t *= A[i]; cx /= A[i]; }
		r *= t;
	}
	return r;
}

long long solve(long long x, long long y) {
	if (y == 1) return 1;
	x %= y;

	long long G = period(y);
	if (x == 0) return y;

	long long E = solve(x, G);
	long long L = modpow(x, E, y);
	
	long long LIM = ((1LL << 62) / y) * y;
	long long X = find_value(G, ((L - E + LIM) % y), y);
	X *= G; X += E;
	return X;
}

int main() {
	long long Q; cin >> Q;
	for (int i = 1; i <= Q; i++) {
		long long A, M; cin >> A >> M;
		long long Z = solve(A, M);
		cout << Z << endl;
	}
	return 0;
}