#include <bits/stdc++.h>
using namespace std;
int n;
typedef long long ll;
int fastmi(ll a,ll k,ll p)
{
int res=1;
while(k)
{
if(k&1)
res=(ll)res*a%p;
k>>1;
a=(ll)a*a%p;//这个地方因为他有一个数学公式(ab)%c=((a%c)(b%c))%c,就是先算出最后的结果在求模跟先把最后结果的每一个因子求模相乘得出一个结果再最后取一次模的结果是一样的
}
return res;
}
int main()
{
cin>>n;
while(n--)
{
ll a,b,p;
cin>>a>>b>>p;
cout<<fastmi(a,b,p)<<endl;
}
return 0;
}