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 <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <string.h>
#include <functional>

using namespace std;
typedef long long llong;

int gcd(int x, int y) {
	if (x < y) swap(x, y);
	if (y == 0) return x;
	return gcd(y, x % y);
}

int phi(int x) {
	int ret = 1;
	for (int i = 2; (llong)i * i <= x; ++i) {
		int cnt = 0;
		while (x % i == 0) x /= i, ret *= i, ++cnt;
		if (cnt) ret = ret / i * (i - 1);
	}
	if (x > 1) ret *= x - 1;
	return ret;
}

llong mul(llong a, llong b, llong m) {
	llong ret = 0ll;
	a %= m;
	while (b) {
		if ((b & 1ll) != 0ll) ret = (ret + a) % m;
		b >>= 1;
		a = (a << 1) % m;
	}
	return ret;
}

llong pow(llong a, llong p, llong m) {
	llong ret = 1ll;
	while (p) {
		if ((p & 1ll) != 0ll) ret = mul(ret, a, m);
		a = mul(a, a, m);
		p >>= 1;
	}
	return ret;
}

llong solve(int a, int m) {
	if (m == 1) return 50;
	int n = m, g;
	while ((g = gcd(a, n)) != 1) n /= g;
	if (n == 1) return m * (50 / m + 1);
	int p = phi(n);
	llong ret = solve(a, p);
	llong mod = (llong)m * p;
	ret = pow(a, ret, mod);
	while (ret < 50) ret += mod;
	return ret;
}

int main() {
	int T, a, m;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &a, &m);
		printf("%lld\n", solve(a, m));
	}
	return 0;
}