#include <iostream> using namespace std; using i64 = long long; inline int add(int x, int y, int mod) { return (x + y) % mod; } inline int mul(int x, int y, int mod) { return i64(x) * y % mod; } int pow(int x, int y, int mod) { int res = 1; for (; y > 0; x = mul(x, x, mod), y >>= 1) { if (y & 1) res = mul(res, x, mod); } return res; } struct Solution { void main() { int n, s, q; cin >> n >> s >> q; int ans = 0; for (int x = 0; x < n; ++x) { if (pow(x, q, n) + mul(x, q, n) == s) ans = add(ans, x, q); } cout << ans << '\n'; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; cin >> t; while (t-- > 0) Solution().main(); return 0; }