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)