#include <cctype>
#include <cstdio>
#include <iostream>

typedef unsigned long long LL;

inline int readInt() {
  LL ans = 0, c, f = 1ull;
  while (!isdigit(c = getchar()))
    if (c == '-') f = -1;
  do ans = ans * 10 + c - '0';
  while (isdigit(c = getchar()));
  return ans * f;
}

const int N = 1e3+7, T = 1e4+3;
LL a, b, f[N * N], n, len, k, t;

inline void Fib() {
  f[0] = 0ull;
  f[1] = 1ull;
  for (LL i = 2; i <= n * n; ++i) {
  	f[i] = (f[i - 1] + f[i - 2]) % n;
  	if (f[i] == 1 && f[i - 1] == 0 ) {
  	  len = i - 1ull;
  	  break;
 	}
  }
}

inline LL Qpow(LL a, LL b) {
  a %= n;
  LL ans = 1;
  while (b) {
  	if(b & 1) ans = (ans * a) % n;
  	a = (a * a) % n;
  	b >>= 1;
  }
  return ans;
}

int main() {
  t = readInt();
  while (t--) {
  	a = readInt(), b = readInt(), n = readInt();
  	if (n == 1|| a == 0) {
  	  printf("0\n");
  	  continue;
	}
    Fib();
    int k = Qpow(a % n, b);
    printf("%llu\n", f[(k + 1) % len - 1]);
  }
  return 0; 
}