n = int(input()) for _ in range(n): a, k, p = map(int, input().split()) res = 1 while k: if k & 1: res = res * a % p k = k >> 1 a = a * a % p print(res)
