for _ in range(int(input())):
    a,b,p=map(int,input().split())
    print(pow(a,b,p))

python的pow函数自带快速幂，但还是自己尝试一下吧