#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll int power(ll int &ans,ll int i,ll int p)
{
if(i==0)
{
return 1;
}
else
{
int subp=power(ans,i/2,p);
if(i&1)
{
return (anssubpsubp)%p;
}
else
{
return (anssubpsubp)%p;
}
}
}
int main() {
int t;
cin>>t;
while(t–)
{
ll int a,n,p;
cin>>a>>n>>p;
ll int ans=a%p;
for(int i=2;i<=n;i++)
{
ans=power(ans,i,p);
}
cout<<ans<<endl;
}
return 0;
}