t = int(input())
def qpow(x,y,mod):
    res = 1
    while y:
        if y & 1:
            res *= x
            res %= mod
        x *= x
        x %= mod
        y >>= 1
    return res % mod

for _ in range(t):
    x,y,p = map(int,input().split())
    print(qpow(x,y,p))