def ksm(a, b, p): # mod p 下的快速幂 res = 1 while b != 0: if b & 1 == 1: res = (res * a) % p a = (a * a) % p b >>= 1 return res q = int(input()) for _ in range(q): a, b, p = map(int, input().split()) print(ksm(a, b, p))