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;

int gcd(int a, int b) {
    while(b)
        swap(a %= b, b);
    return a;
}
long inv(int a, int m) {
    long i = 1, j = 0;
    for(int b = m; a > 1; swap(i, j), swap(a, b)) {
        j = (j + b / a * (m - i)) % m;
        b %= a;
    }
    return i;
}
long po(long a, int n, int m) {
    long r = 1;
    for(; n; n >>= 1, (a *= a) %= m)
        if(n & 1)
            (r *= a) %= m;
    return r;
}
void fa(int m, map<int, int> &f) {
    for(int p = 2; p * p <= m; p++) {
        if(m % p)
            continue;
        f[p] = 1;
        while(m % p == 0)
            m /= p, f[p] *= p;
    }
    if(m > 1)
        f[m] = m;
}
long tet(long a, int m) {
    if(m < 2)
        return 0;
    map<int, int> f;
    fa(m, f);
    int n = 1, ph = 1;
    for(auto i : f) {
        int p, q;
        tie(p, q) = i;
        if(a % p)
            m /= q, n *= q, ph *= q / p * (p - 1);
    }
    return po(a, tet(a, ph), n) * inv(m, n) % n * m;
}
int main() {
    int Q;
    cin >> Q;
    for(int j = 0; j < Q; j++) {
        int a, m;
        cin >> a >> m;
        map<int, int> f;
        fa(m, f);
        int n = 1, ph = 1;
        long l = m;
        for(auto i : f) {
            int p, q;
            tie(p, q) = i;
            if(a % p)
                m /= q, n *= q, ph *= q / p * (p - 1);
        }
        auto t = tet(a, ph);
        auto s = po(a, t, n) * inv(m, n) % n * m;
        int x = 1;
        for(auto i : f) {
            int q = i.second;
            if(ph % q)
                x *= q;
        }
        l *= ph / gcd(l, ph);
        int y = l / x;
        cout << (s * inv(y, x) % x * y + t * inv(x, y) % y * x) % l + l << endl;
    }
    return 0;
}