n =  int(input())

def qpow(a,n,p):
    
    if n == 0:
        return 1
    elif n%2 == 1:
        return qpow(a, n-1,p) * a % p
    else:
        temp = qpow(a,n/2,p)
        return temp * temp % p

for i in range(n):
    
    a,b,p = map(int,input().split())
    
    print(qpow(a, b,p))