#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//快速幂
//将B化成二进制,如5的11次方,11的二进制为1011
//将B的二进制中为1的位置对应的A的2的k次幂相乘,得到最终结果。
int quickpow(LL a,LL n,LL p)
{
LL ans = 1;
for(; n ;n >>= 1)
{
if(n & 1)
ans *= a,ans %= p;
a *= a;
a %= p;
}
return ans;
}
int main() {
int T;
cin >> T;
while(T--)
{
LL A,B,P;
cin >> A >> B >> P;
cout << quickpow(A,B,P) << endl;
}
}