#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
ll a,b,n,ans=1;
cin>>a>>b>>n;
for (ll i=0;i<b;i++)
{
ans=ans%n*a%n;
}
cout<<ans%n<<endl;
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdHlwZWRlZiBsb25nIGxvbmcgbGw7CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBtYWluKCkKewoJaW50IHQ7CgljaW4+PnQ7Cgl3aGlsZSh0LS0pCgl7CgkJbGwgYSxiLG4sYW5zPTE7CgkJY2luPj5hPj5iPj5uOwoJCWZvciAobGwgaT0wO2k8YjtpKyspCgkJewoJCQlhbnM9YW5zJW4qYSVuOwoJCX0KCQljb3V0PDxhbnMlbjw8ZW5kbDsKCX0KfQo=