def legendre(a, p): return pow(a, (p - 1) // 2, p) # https://rosettacode.org/wiki/Tonelli-Shanks_algorithm#Python def tonelli(n, p): if legendre(n, p) != 1: return [] assert(p != 2) q = p - 1 s = 0 while q % 2 == 0: q //= 2 s += 1 if s == 1: result = pow(n, (p + 1) // 4, p) assert(result != 0) return [result, p - result] for z in range(2, p): if p - 1 == legendre(z, p): break c = pow(z, q, p) r = pow(n, (q + 1) // 2, p) t = pow(n, q, p) m = s t2 = 0 while (t - 1) % p != 0: t2 = (t * t) % p for i in range(1, m): if (t2 - 1) % p == 0: break t2 = (t2 * t2) % p b = pow(c, 1 << (m - i - 1), p) r = (r * b) % p c = (b * b) % p t = (t * c) % p m = i assert(r != 0) return [r, p - r] memo = {} def solve_two(a, n, p): if a == 0: return [0] if n == 1: return [a] if legendre(a, p) != 1: return [] if (a, n, p) in memo: return memo[(a, n, p)] result = [] for x in tonelli(a, p): assert(pow(x, 2, p) == a) result += solve_two(x, n // 2, p) memo[(a, n, p)] = result return result def extgcd(a, b): if b == 0: return (1, 0) else: x, y = extgcd(b, a % b) return (y, x - (a // b) * y) def solve_odd(a, n, p): e = extgcd(n, p - 1)[0] % (p - 1) return pow(a, e, p) def solve(a, n, p): if p == 2: return [x for x in range(2) if pow(x, n, p) == a] m = n e = 1 while m % 2 == 0: m //= 2 e *= 2 b = solve_odd(a, m, p) c = solve_two(b, e, p) return [x for x in c if pow(x, n, p) == a] T = int(input()) for _ in range(T): p, k, a = map(int, input().split()) answer = solve(a, k, p) if len(answer) == 0: print(-1) else: print(answer[0])