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<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

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

LL safe_mul(LL x, LL y, LL mod) {
    x %= mod;
    y %= mod;
    LL r = 0;
    for (; y; y>>=1) {
	if (y&1) {
	    r += x;
	    if (r >= mod) r -= mod;
	}
	x += x;
	if (x >= mod) x -= mod;
    }
    return r;
}

LL powMod(LL x, LL y, LL mod) {
    x %= mod;
    LL r = 1;
    for (; y; y>>=1) {
	if (y&1) r = safe_mul(r, x, mod);
	x = safe_mul(x, x, mod);
    }
    return r % mod;
}

LL rec(LL A, LL M) {
    if (M == 1) {
	return 2;
    }

    LL ph = phi(M);
    LL r = rec(A, ph);
    LL k = powMod(A, r, M*ph) + M * ph;
    // A^r == r (mod phi(M));
    // A^(A^r) == A^r (mod M);
    return k;
}

void MAIN() {
    LL A, M;
    scanf("%lld%lld", &A, &M);
    LL k = rec(A, M);
    printf("%lld\n", k);
//    eprintf("%lld %lld\n", powMod(A, k, M), k % M);
}

int main() {
    int TC = 1;
    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}