#include using namespace std; using lint = long long; template Z ext_gcd(Z a, Z b, Z& x, Z& y) { Z u = y = 0, v = x = 1; while (b) { Z q = a / b; swap(a -= q * b, b); swap(x -= q * u, u); swap(y -= q * v, v); } return a; } lint tmod(lint a, lint p) { return (a %= p) < 0 ? a + p : a; } lint mod_inv(lint a, lint p) { a = tmod(a, p); lint b = p, x = 1, u = 0; while (b) { lint q = a / b; swap(a -= q * b, b); swap(x -= q * u, u); } return a == 1 ? tmod(x, p) : -1; } lint mod_pow(lint a, lint n, lint p) { assert(n >= 0); a = tmod(a, p); lint res = 1; while (n) { if (n & 1) (res *= a) %= p; (a *= a) %= p; n >>= 1; } return res; } lint mod_log(lint g, lint x, lint p) { g = tmod(g, p); x = tmod(x, p); int m = ceil(sqrt(p - 1)); map mp; lint a = 1; for (int j = 0; j < m; ++j) { mp[a] = j; (a *= g) %= p; } g = mod_inv(mod_pow(g, m, p), p), a = 1; for (int i = 0; i < (p - 1 + m - 1) / m; ++i) { if (mp.count(a * x % p)) { return i * m + mp[a * x % p]; } (a *= g) %= p; } return -1; } int mod_root(lint a, lint n, int p, int g) { a = tmod(a, p); if (a == 0) { return n > 0 ? 0 : -1; } n = tmod(n, p - 1); int e = mod_log(g, a, p); assert(e != -1); lint x, y; int d = ext_gcd(n, p - 1, x, y); if (e % d) return -1; return mod_pow(g, e / d * x + (lint)1e18 / (p - 1) * (p - 1), p); } template map factorize(Z n) { map res; for (Z i = 2; i * i <= n; ++i) while (n % i == 0) ++res[i], n /= i; if (n != 1) ++res[n]; return res; } int main() { int t; cin >> t; while (t--) { lint p, k, a; cin >> p >> k >> a; auto mp = factorize(p - 1); auto mod_ord = [&](lint x) -> lint { if (mod_pow(x, p - 1, p) != 1) return -1; lint res = p - 1; for (const auto& e : mp) { for (int i = 0; i < e.second; ++i) { if (mod_pow(x, res / e.first, p) == 1) { res /= e.first; } else break; } } return res; }; lint g = 1; while (mod_ord(g) != p - 1) { ++g; } cout << mod_root(a, k, p, g) << '\n'; } }