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;
 
typedef long long LL;
typedef pair<int, int> pii;
 
#define fst first
#define snd second
#define pb push_back
#define REP(i, a, b)  for(int i = (a), i##end = (b); i < i##end; ++i)
#define DREP(i, a, b) for(int i=(a-1), i##end = (b); i >=i##end; --i)
 
template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
 
const int N = 100000;
const int oo = 0x3f3f3f3f;
 
template<typename T> T read() {
    T n(0), f(1);
    char ch = getchar();
    for( ;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for( ; isdigit(ch); ch = getchar()) n = n * 10 + ch - 48; 
    return n * f;
}
 
LL fpm(LL a, LL b, LL mod) {
    LL res = 1;
    for(; b > 0; b >>= 1) {
        if(b & 1)
            res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
 
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
 
LL exgcd(int a, int b, LL& x, LL& y) {
    if(!b) {
        x = 1;
        y = 0;
        return a;
    }
 
    LL g = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
 
    return g;
}
 
int phi(int n) {
    int res = n;
    for(int i = 2; i * i <= n; ++i) if(n % i == 0) {
        res = res / i * (i - 1);
        while(n % i == 0) n /= i;
    }
    if(n > 1) res = res / n * (n - 1);
    return res;
}
 
LL solve(int a, int m) {
    if(m <= 500) {
        int x = a;
        for(int i = 1; ; i++) {
            if(x == i % m) return i;
            x = 1LL * x * a % m;
        }
    }
    
    int p = phi(m);
    int r = gcd(m, p);
    LL t = solve(a, r), a_t = fpm(a, t, m), x, y, l = p / r;
 
    exgcd(m / r, p / r, x, y);
 
    x *= (((t - a_t) % p + p) % p) / r;
    x = (x % l + l) % l + l;
    LL res = x * m + a_t;

    return res;
}
 
void write(LL x) {
    if(x) { 
        write(x / 10);
        putchar(x % 10 + '0');
    }
}
 
int main() {
#ifdef Wearry
    freopen("data.txt", "r", stdin);
    freopen("ans.txt", "w", stdout);
#endif
 
    for(int T = read<int>(); T--; ) {
        static int a, m;
        a = read<int>();
        m = read<int>();
        LL k = solve(a, m);
        write(k); putchar(10);
    }
 
    return 0;
}