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 <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
#include<cassert>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;
const long double eps = 1E-14;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

mint pw(mint a, ll b) {
	if (b == 0) { return 1; }
	mint ret = pw(a, b >> 1);
	ret *= ret;
	if (b & 1) { ret *= a; }
	return ret;
}

typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;

typedef vector<mint> vmint;
typedef vector<vector<mint>> vvmint;
typedef vector<vector<vector<mint>>> vvvmint;

/////////////////////////////////////
ll extGCD(ll a, ll b, ll& x, ll& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	ll d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

pair<ll, ll> chrem(ll a1, ll m1, ll a2, ll m2) {
	if (m1 < m2) { return chrem(a2, m2, a1, m1); }

	ll p, q;
	ll d = extGCD(m1, m2, p, q);
	if ((a2 - a1) % d != 0) { return { -1,-1 }; }

	ll m = m1 / d * m2;
	ll x = (a2 - a1) / d  * p % (m2 / d);
	//cout << m1 <<" "<< x << endl;
	ll r = a1 + m1 * x;
	//cout << r << endl;
	r = (r % m + m) % m;

	return { r,m };
}

ll beki(ll x, ll y, ll m) {
	if (y == 0) { return 1; }
	
	ll c = beki(x, y/2, m);
	c = c * c;
	if (m > 0) { c %= m; }
	if (y % 2 == 1) { c *= x; }
	if (m > 0) { c %= m; }

	return c;
}

pair<ll,ll> subsol(ll a, ll p, ll b, ll x) {//m=p^b,mod(p-1)でxであるような解
	if (a % p == 0) {
		auto ret = chrem(x, p - 1, 0, beki(p, b,0));
		return ret;
	}

	repn(i, b) {
		ll P = beki(p, i, 0);

		ll k = beki(a, x, P) - x;
		k = ((k % P) + P) % P;
		k /= beki(p, i - 1, 0);

		if (k > 0) { x += (p - 1) * beki(p, i - 1, 0) * (p - k); }
	}


	ll ans = x + (p - 1) * beki(p, b, 0);
	ll m = beki(p, b, 0);
	//cout << a <<" "<< m<<" " << x << endl;
	assert((beki(a, ans, m) - ans) % m == 0);

	return { x,(p - 1) * beki(p,b,0) };
}

pair<ll,ll> solve(ll a, ll m) {

	if (m == 1) { return { 0,1 }; }
	
	ll x = m;
	ll p = 1;
	for (ll i = 2; i * i <= m; i++) {
		if (x % i == 0) {
			p = i;
			while (x % i == 0) { x /= i; }
		}
	}
	p = max(p, x);

	ll b = 0;
	ll r = m;
	while (r % p == 0) {//m=r*p^b
		r /= p;
		b++;
	}

	
	auto Q = solve(a, r);
	auto P = subsol(a, p, b, Q.first % (p - 1));

	//cout << Q.first % (p - 1) << endl;
	//cout << r << " " << p << " " << b << endl;

	//cout << Q.first << " " << Q.second << " " << P.first << " " << P.second << endl;
	auto ret = chrem(Q.first, Q.second, P.first, P.second);
	//cout << ret.first << endl;
	//cout << ret.first % Q.second << " " << ret.first % P.second << endl;
	assert(ret.first % Q.second == Q.first && ret.first % P.second == P.first);
	
	//cout << a << " " << m << endl;
	ll ans = ret.first + ret.second;
	assert((beki(a, ans, m) - ans) % m == 0);

	return ret;
	

}

int main() {
	ll Q;
	cin >> Q;

	repn(q, Q) {
		ll a, m;
		cin >> a >> m;

		auto P = solve(a, m);
		ll ans = P.first + P.second;

		assert((beki(a, ans, m) - ans) % m == 0);
		cout << P.first + P.second << endl;
	}
}