q = int(input())
# 补充余数运算性质
# (a*b) mod p = [(a mod p)*(b mod p)] mod p
def function1(a,b,p):
    if b == 0: return 1
    if b%2 == 1:
        res = function1(a,b-1,p)
        return res*a % p
    else:
        res = function1(a,b//2,p) % p
        return res*res % p
for _ in range(q):
    a,b,p = map(int,input().split())
    print(function1(a,b,p))