from functools import partial

print = partial(print, flush=True)


def legendre(a, p):
    ls = pow(a, (p - 1) // 2, p)
    return -1 if ls == p-1 else ls

def mod_sqrt(a, p):
    if legendre(a, p) != 1:
        return 0
    elif a == 0:
        return 0
    elif p == 2:
        return 0
    elif p % 4 == 3:
        return pow(a, (p+1) // 4, p)

    s = p - 1
    e = 0
    while s % 2 == 0:
        s >>= 1
        e += 1

    n = 2
    while legendre(n, p) != -1:
        n += 1

    x = pow(a, (s+1) // 2, p)
    b = pow(a, s, p)
    g = pow(n, s, p)
    r = e

    while True:
        t = b
        m = 0
        for m in range(r):
            if t == 1:
                break
            t = pow(t, 2, p)

        if m == 0:
            return x

        gs = pow(g, 2 ** (r-m-1), p)
        g = (gs*gs) % p
        x = (x*gs) % p
        b = (b*g) % p
        r = m

t = int(input())

for i in range(t):
    p, k, a = map(int, input().split())
    if p == 2:
        print(1)
        continue
    m = 0
    n = k
    while n%2 == 0:
        m += 1
        n //= 2
    try:
        l = pow(n, -1, p-1)
    except:
        print(-1)
        continue
    x = pow(a, l, p)
    for _ in range(m):
        x = mod_sqrt(x, p)
    if x != 0:
        print(x)
    else:
        print(-1)