原来python也有位运算
def quick(a,b,p):
ans=1;
while b>0:
if b&1:
ans=(ans*a)%p;
a=(a*a)%p;
b=b>>1;
return ans;
n=int(input());
for i in range(n):
a,b,p=list(map(int,input().split()));
#print('{} {} {}'.format(a,b,p));
print(quick(a,b,p));