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 <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;
 
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
 
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }



inline long long mod(long long a, long long m) {
	return (a % m + m) % m;
}

long long pow(long long a, long long n, long long m) {
	if (n == 0) return 1 % m;
	long long t = pow(a, n / 2, m);
	t = mod(t * t, m);
	if (n & 1) t = mod(t * a, m);
	return t;
}

vector<pair<long long, long long> > prime_factor(long long n) {
	vector<pair<long long, long long> > res;
	for (long long i = 2; i*i <= n; ++i) {
		if (n % i == 0) {
			int exp = 0;
			while (n % i == 0) {
				++exp;
				n /= i;
			}
			res.push_back(make_pair(i, exp));
		}
	}
	if (n != 1) res.push_back(make_pair(n, 1));
	return res;
}

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

long long LCM(long long a, long long b) {
	long long g = GCD(a, b);
	return a / g * b;
}

vector<pair<long long, long long> > divA;





long long inv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t*b; swap(a, b);
		u -= t*v; swap(u, v);
	}
	return mod(u, m);
}

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

pair<long long, long long> ChineseRem(long long b1, long long m1, long long b2, long long m2) {
	long long x = 0, m = 1;
	long long a = m, b = b1 - x, d = gcd(m1, a);
	if (b % d != 0) return make_pair(0, -1);
	long long t = mod(b / d * inv(a / d, m1 / d), m1 / d);
	x += m * t;
	m *= m1 / d;
	a = m, b = b2 - x, d = gcd(m2, a);
	if (b % d != 0) return make_pair(0, -1);
	t = mod(b / d * inv(a / d, m2 / d), m2 / d);
	x += m * t;
	m *= m2 / d;
	return make_pair(x % m, m);
}





long long solve(long long A, long long M) {
	if (A == 0) return M;
	if (A == 1) return 1;
	if (M == 1) return 50;

	long long nM = M;
	for (int i = 0; i < divA.size(); ++i) {
		long long p = divA[i].first;
		while (nM % p == 0) nM /= p;
	}

	vector<pair<long long, long long> > divM = prime_factor(nM);
	for (int i = 0; i < divM.size(); ++i) {
		long long p = divM[i].first;
		nM *= p - 1;
		nM /= p;
	}


	long long y = solve(A, nM);
	long long rM = pow(A, y, M);
	long long rnM = pow(A, y, nM);
	pair<long long, long long> pres = ChineseRem(rM, M, rnM, nM);

	long long lcm = pres.second;
	long long res = pres.first;
	while (res < 50) res += lcm;

	/*
	COUT(M);
	COUT(divM);
	COUT(nM);
	COUT(lcm);
	COUT(res);
	COUT(mod(res, M));
	COUT(pow(A, res, M));
	*/

	return res;
}


int main() {
	int Q;
	while (cin >> Q) {
		for (int i = 0; i < Q; ++i) {
			long long a, m; cin >> a >> m;
			divA = prime_factor(a);
			long long res = solve(a, m);
			cout << res << endl;

			/*
			COUT(divA);
			COUT(mod(res, m));
			COUT(pow(a, res, m));
			*/
		}
	}
}