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 PYTHON):

Solution:
def egcd(a, b):
    aa = 1; ab = 0
    ba = 0; bb = 1
    while b:
        q = a // b
        r = a % b
        ra = aa - ba * q
        rb = ab - bb * q
        a, b = b, r
        aa, ab = ba, bb
        ba, bb = ra, rb
    return a, aa, ab


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b): return a // gcd(a, b) * b


def phi(n):
    r = 1
    i = 1
    while n > 1:
        i += 1
        if i*i > n: i = n
        x = 1
        while n % i == 0: n //= i; r *= i - x; x = 0
    return r


def inftowermod(n, m):
    if m == 1: return 0
    if n == 1: return 1
    phim = phi(m)
    return pow(n, inftowermod(n, phim) + phim, m)


def solve_congruence(a1, m1, a2, m2):
    if m2 % m1 == 0: return a2
    if m1 % m2 == 0: return a1
    g, p, q = egcd(m1, m2)
    lm = m1 // g * m2
    w1 = m2 // g * q % lm
    w2 = m1 // g * p % lm
    return ((a1 // g * w1 + a2 // g * w2) * g + a1 % g) % lm


def solve(a, m):
    if a == 0: return m
    phim = phi(m)
    kphim = inftowermod(a, phim)
    km = pow(a, phim + kphim, m)


    ans = solve_congruence(km, m, kphim, phim)
    if ans < phim: ans += lcm(m, phim)
    return ans


for __ in range(int(raw_input())):
    print solve(*map(int, raw_input().split()))