#include <iostream>

int main(int argc, char *argv[]) {
  long long count, a, b, q;
  
  std::cin >> count;
  
  while (--count >= 0) {
    std::cin >> a >> b >> q;
    
    long long res = 1;
    
    while (b) {
      if (b & 1) {
        //  res存放的全是奇数个的乘积，最后移位一定是1，这样将前面累积的偶数幂乘上去
        res = (res * a) % q;
      }
      //  每次移动移位，减少一个平方幂
      a = (a * a) % q;
      b >>= 1;
    }
    
    std::cout << res << std::endl;
  }
  
  return 0;
}