n = int(input())

def qmi(a,b,c):
    r = 1
    while b:
        if b & 1:
            r = r * a % c
        b = b >> 1
        a = a * a % c
    return r


while n:
    a,b,c = map(int,input().split())
    print(qmi(a,b,c))
    n -= 1