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 <bits/stdc++.h>
#define ADD(a, b) a = (a + (ll)b) % mod
#define MUL(a, b) a = (a * (ll)b) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define rer(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> ppi;
typedef vector<ll> vi;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest) { 
	cout << arg << " "; Debug(rest...); }
template<class T>ostream& operator<< (ostream& out, const vector<T>& v) {
	out << "[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<< ", ";out<<v.back();}out << "]";return out;}
template<class S, class T>ostream& operator<< (ostream& out, const pair<S, T>& v) {
	out << "(" << v.first << ", " << v.second << ")";return out;}
const int MAX_N = 200010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

ll phi(ll M) {
	ll A = M;
	for(ll i = 2; i * i <= A; i++) {
		if(A % i == 0) {
			M = M / i * (i - 1);
			while(A % i == 0) A /= i;
		}
	}
	if(A != 1) M = M / A * (A - 1);
	return M;
}

ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}

ll extgcd(ll a, ll b, ll& x, ll& y) { //get(ax + by = gcd(a, b))
	if(b == 0) {
		x = 1; y = 0;
		return a;
	}
	ll res = extgcd(b, a % b, y, x);
	y -= (a / b) * x;
	return res;
}

ll mod_pow(ll a, ll n, ll mod) { //get a^n mod
	if(n == 0) return 1;
	ll res = mod_pow(a, n / 2, mod);
	if(n % 2 == 0) return res * res % mod;
	else return a * res % mod * res % mod;
}

ll mod_inv(ll a, ll m) { //get x such that ax=gcd(a, m)(modm)
	ll x, y;
	extgcd(a, m, x, y);
	return (x % m + m) % m;
}

int Q;
ll A, M;

ll loop(ll A, ll M) {
	if(M == 1) return 10000;
	ll K = loop(A, phi(M));
	ll tK = mod_pow(A, K, M);
	return tK + (tK < 100 ? M : 0);
}

void solve() {
	cin >> Q;
	while(Q--) {
		cin >> A >> M;
		ll pM = phi(M);
		ll K = loop(A, M) % M;
		ll pK = loop(A, pM) % pM;
		ll pt = mod_inv(M, pM);
		ll g = gcd(M, pM), l = M * pM / g;
		ll t = ((pK - K) / g * pt) % pM;
		//debug(M, pM, K, pK, pt, g, l, t);
		ll pans = ((t * M % l + K) % l + l) % l;
		ll ans = pans < 100 ? pans + l : pans;
		cout << ans << "\n";
		//debug(mod_pow(A, ans, M), ans % M);
	}
}


int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(5);
#ifdef LOCAL
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}