题解 | #快速幂#

# https://zhuanlan.zhihu.com/p/95902286
"""
重要的是2点：
#####s1:
a^n = (1) n是奇数， a^(n-1) x a
      (2) 偶数， (a^n/2) ^2
######s2:
取模的公式：
（aXb）mod c = (a mod c x b mod c)mod c
"""
times = int(input())
listall = []

def quickpow(a,b,p):
    if b == 0:
        return 1
    if b%2==1:
        return quickpow(a, b-1,p) *a % p
    else:
        # 此步骤tmp不可省略，因为计算量减半
        tmp = quickpow(a,b/2,p)%p
        return tmp*tmp%p

for i in range(times):
    a,b,p = map(int, input().split())
    elema = quickpow(a,b,p)
    res = elema%p
    print(res)