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:
// vim:ts=4:sts=4:sw=4:et
// MOSCOW IPT JINOTEGA
// Table #14
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i = 0; i < int(n); ++i)
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
typedef long double ld;
typedef long long ll;
typedef long long i64;


//int add(int x) {  
    //return x;
//}

//template<typename... T>
//int add(int mod, int x, T... y) {  
    //x += add(y...);
    //if (x >= mod)
            //x -= mod;
    //return x;
//}

//template<typename... T>
//int udd(int mod, int &x, T... y) { 
    //return x = add(mod, x, y...);
//}

//template<typename... T>
//int sub(int mod, int x, T... y) { 
    //return add(mod, x, mod - add(mod, y...));
//}

//int mul(int x) { 
    //return x;
//}

//template<typename... T>
//int mul(int mod, int x, T... y) { 
    //return 1ll * x * mul(mod, y...) % mod;
//}

int mul(int mod, int x, int y) {
    return 1ll * x * y % mod;
}

int bin(int mod, int x, ll to) { 
    x %= mod;
    int y = 1;
    while (to) { 
            if (to & 1)
                        y = mul(mod, x, y);
                x = mul(mod, x, x);
                    to >>= 1;
    }
    return y;
}

ll gcd(ll a, ll b, ll &x, ll &y) {
    if (a == 0) {
        x = 0, y = 1;
        return b;
    }
    ll x1, y1;
    ll g = gcd(b % a, a, x1, y1);
    x = y1 - x1 * (b / a);
    y = x1;
    assert(a * x + b * y == g);
    return g;
}
ll crt(ll mod1, ll mod2, ll rem1, ll rem2) {
    //cerr << mod1 << " -> " << rem1 << endl;
    //cerr << mod2 << " -> " << rem2 << endl;
    ll r = (rem2 - (rem1 % mod2) + mod2) % mod2;
    ll x, y;
    ll g = gcd(mod1, mod2, x, y);
    assert(r % g == 0);

    x %= mod2;
    if (x < 0)
        x += mod2;

    ll ans = (x * (r / g)) % mod2;
    ans = ans * mod1 + rem1;

    assert(ans % mod1 == rem1);
    assert(ans % mod2 == rem2);
    return ans;
}


int phi(int n) {
    int ans = 1;
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0) {
            n /= i;
            ans *= i - 1;
            while (n % i == 0) {
                n /= i;
                ans *= i;
            }
        }
    if (n > 1)
        ans *= n - 1;
    return ans;
}

int a, m;
int n;
vector<int> b;

vector<int> nxt(const vector<int> &x) {
    vector<int> y(n);
    for (int i = 0; i < n; ++i)
        if (i + 1 < n) {
            y[i] = bin(b[i], a, x[i + 1] + b[i + 1]);
        } else {
            y[i] = 0;
        }
    return y;
}

void read() {
    cin >> a >> m;
}

void kill() {
    b.clear();

    if (a == 0) {
        cout << m << endl;
        return;
    }

    if (m == 1) {
        cout << 1 << endl;
        return;
    }

    while (m > 1) {
        b.push_back(m);
        m = phi(m);
        ++n;
    }
    b.push_back(1);
    n = b.size();

    vector<int> cur(n);
    for (int i = 0; i < n; ++i)
        cur[i] = a % b[i];

    vector<int> prev(n, -1);

    while (prev != cur) {
        //for (int i = 0; i < n; ++i)
            //cerr << cur[i] << " ";
        //cerr << endl;
        prev = nxt(cur);
        swap(prev, cur);
    }

    ll ans = crt(b[0], b[1], cur[0], cur[1]) + 1ll * b[0] * b[1];
    assert(ans % b[0] == bin(b[0], a, ans));
    cout << ans << endl;

    //cout << cur[0] << " " << cur[1] << endl;
}

int main() {
#ifdef LOCAL
    assert(freopen("f.in", "r", stdin));
#endif
    //ios_base::sync_with_stdio(false);

    int t;
    cin >> t;
    while (t--) {
        read();
        kill();
    }

    return 0;
}