//---------Think twice code once----------/
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll power(ll a,ll b,ll m)
{
ll mul=1;
a=(a%m);
while(b>0)
{
if(b&1)
{
mul=((mul%m*a%m)%m);
}
b=b>>1;
a=((a*a)%m);
}
return mul;
}
int main()
{
int t;
cin>>t;
while(t--)
{
ll a,b,n,ans;
cin>>a>>b>>n;
ans=power(a,b,n);
cout<<ans%n<<endl;
}
}
Ly8tLS0tLS0tLS1UaGluayB0d2ljZSBjb2RlIG9uY2UtLS0tLS0tLS0tLwojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKbGwgcG93ZXIobGwgYSxsbCBiLGxsIG0pCnsKCWxsIG11bD0xOwoJYT0oYSVtKTsKCXdoaWxlKGI+MCkKCXsKCQlpZihiJjEpCgkJewoJCQltdWw9KChtdWwlbSphJW0pJW0pOwoJCX0KCQliPWI+PjE7CgkJYT0oKGEqYSklbSk7Cgl9CglyZXR1cm4gbXVsOwp9CmludCBtYWluKCkKewoJaW50IHQ7CgljaW4+PnQ7Cgl3aGlsZSh0LS0pCgl7CgkJbGwgYSxiLG4sYW5zOwoJCWNpbj4+YT4+Yj4+bjsKCQlhbnM9cG93ZXIoYSxiLG4pOwoJCWNvdXQ8PGFucyVuPDxlbmRsOwoJfQp9Cg==