#include<bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
constexpr int BSZ = 1024;
using UINT = number<cpp_int_backend<BSZ, BSZ, unsigned_magnitude, unchecked, void>>;
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

constexpr int M = 1e6 + 100;
int lpf[M], phi[M];

void prepare_primes() {
  memset(lpf, -1, sizeof(lpf));
  VI primes;
  phi[1] = 1;
  for (int i = 2; i < M; i++) {
    int p = lpf[i];
    if (p == -1) {
      primes.emplace_back(i);
      p = lpf[i] = i;
      phi[i] = i - 1;
    }
    for (int q : primes) {
      int j = i * q;
      if (j >= M) break;
      lpf[j] = q;
      if (q == p) {
        phi[j] = phi[i] * p;
        break;
      }
      phi[j] = phi[i] * (q - 1);
    }
  }
}

int get_ord(int b, int m) {
  using mint = modint;
  modint::set_mod(b);
  int res = phi[b];
  int tmp = res;
  while (tmp != 1) {
    int p = lpf[tmp], e = 0, pe = 1;
    while (tmp % p == 0) tmp /= p, e++, pe *= p;
    res /= pe;
    mint m2res = mint(m).pow(res);
    while (m2res != 1) {
      res *= p;
      m2res = m2res.pow(p);
    }
  }
  return res;
}

int solve(int b, int n, int m) {
  if (gcd(b, m) != 1) return -1;
  int t = get_ord(b, m);
  int c = 0, g = b;
  while (t != 1) {
    g = gcd(g, t);
    if (g == 1) return -1;
    t /= g;
    c++;
  }
  c = max(c + 1, n);
  UINT bc = 1;
  rep(_, c) bc *= b;
  UINT bcn = bc;
  rep(_, n) bcn *= b;
  UINT mbc = [&]() {
    UINT mbc = 1;
    auto k = bc;
    UINT mm = m;
    while (k) {
      if (k & 1) mbc = (mbc * mm) % bcn;
      k >>= 1;
      mm = (mm * mm) % bcn;
    }
    return mbc;
  }();
  auto q = mbc / bc, r = mbc - q * bc;
  if (r != 1) return -1;
  return int(q);
}

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  prepare_primes();
  int tt;
  cin >> tt;
  while (tt--) {
    int b, n, m;
    cin >> b >> n >> m;
    cout << solve(b, n, m) << '\n';
  }
}