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>
using namespace std;

struct Benri { Benri() { std::cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12);}} benri;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<long long>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using ull = unsigned long long;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second

template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }

constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
//constexpr int INF = 1001001001;
constexpr ll INF = 1001001001001001001ll;
constexpr double EPS = 1e-10;
using number = long long;




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

inline ll mul(ll a, ll b, ll m) {
    a = mod(a, m); b = mod(b, m);
    if (b == 0) return 0;
    ll res = mul(mod(a + a, m), b >> 1, m);
    if (b & 1) res = mod(res + a, m);
    return res;
}

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

/*
vector<pair<ll, ll> > prime_factor(ll n) {
    vector<pair<ll, ll> > res;
    for (ll 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;
}*/
number euler_phi(number n) {
    number ret = n;
    for (number i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ret -= ret / i;
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) ret -= ret / n;
    return ret;
}

number GCD(number a, number b) { return b != 0 ? GCD(b, a % b) : a;}
number LCM(number a, number b) { return a * (b / GCD(a, b)); }


const ll L = 50;
ll solve(ll A, ll M) {
    if (A == 0) return M;
    if (A == 1) return 1;
    if (M == 1) return L;
    ll phiM = euler_phi(M);
    /*vector<pair<ll, ll> > divM = prime_factor(M);
    for (int i = 0; i < divM.size(); ++i) {
        ll p = divM[i].first;
        phiM *= p - 1;
        phiM /= p;
    }*/
    ll y = solve(A, phiM);
    ll lcm = LCM(phiM, M);
    ll res = pow(A, y, lcm);
    while (res < L) res += lcm;
    return res;
}

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

    rep(i, Q) {
        ll a, m; cin >> a >> m;
        ll res = solve(a, m);
        cout << res << endl;
    }
}