题解 | 快速幂

import sys
q=int(sys.stdin.readline())

# (m * n) mod p = ((m mod p) * (n mod p)) mod p
# def fast_pow(a,b,p): #1.递归版本
#     if b==1:
#         return a%p
#     elif b%2==0:
#         return (fast_pow(a,b//2,p)**2)%p
#     else:
#         return (a*fast_pow(a,b//2,p)**2)%p

# def fast_pow(a,b,p): #2.位运算版本
#     if b==0:
#         return 1
#     half=fast_pow(a,b>>1,p)
#     res=(half*half)%p
#     if b&1:
#         res=(res*(a%p))%p
#     return res

def fast_pow(a, b, p): #3.迭代版本
    res=1 #b = b_0 \times 2^0 + b_1 \times 2^1 + b_2 \times 2^2 + \cdots + b_k \times 2^k
    base=a%p
    while b>0:
        if b&1:#是奇数的话
            res=(res*base)%p
        b>>=1 #相当于除以2
        base=(base*base)%p
    return res
    


for i in range(q):
    a,b,p=map(int, sys.stdin.readline().split())
    print(fast_pow(a,b,p))