// MODEX solution by Martin Henz, adapted
// from solution by Melvin Zhang

#include <stdio.h>

// Facts on mod:
// b = (b div n) n + (b mod n)
// (a n + b) mod n = b mod n
// Thus:
// (a b) mod n = (a (b mod n)) mod n
//
// Therefore, instead of calculating x^y, 
// we can calculate x^y mod n as follows:
// If y = 0, the result is 1
// If y is odd, the result is
//    (x (x^(y-1) mod n)) mod n
// If y is even, the result is
// (( x^(y/2) mod n) ( x^(y/2) mod n)) mod n
// This leads to the following recursive function:
int modex(int x, int y, int n) {
  if (y==0) return 1;
  if (y % 2) return (x * modex(x,y-1,n)) % n;
  int r = modex(x, y/2, n);
  return (r * r) % n;
}

// The main function simply calls modex() for each test case
int main() {
  int t,i,x,y,n;
  // read the number of test cases into t
  scanf("%d", &t);
  // iterate through the test cases and call modex for each
  for (i=0;i<t;i++) {
    scanf("%d %d %d", &x, &y, &n);
    printf("%d\n",modex(x,y,n));
  }
  return 0;
}