super_log

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const ll maxx = 1e6+100;
ll phi[maxx];
ll mods(ll x,ll mod){
  if(x < mod)
      return x;
  return x%mod+mod;
}
void init(){
  for(ll i=2;i<maxx;i++){
      if(!phi[i])
          for(ll j=i;j<maxx;j+=i){
              if(!phi[j])
                  phi[j] = j;
              phi[j] = phi[j]/i*(i-1);
          }
  }
}
ll pow_mod(ll a,ll b,ll mod){
  ll cnt=1;
  while(b){
      if(b&1)
          cnt=mods(cnt*a,mod);
      a=mods(a*a,mod);
      b>>=1;
  }
  return cnt;//这里就不要取模了
}
ll solve(ll a,ll b,ll mod)
{
  if(mod == 1)
      return 1;
  if(b == 0)
      return 1;
  ll p = phi[mod];
  ll x = solve(a,b-1,p);
  return pow_mod(a,x,mod);
}
int main()
{
  int t;
  phi[0]=0,phi[1]=1;
  init();
  scanf("%d",&t);
  while(t--)
  {
      ll a,b,mod;
      scanf("%lld%lld%lld",&a,&b,&mod);
      printf("%lld\n",solve(a,b,mod)%mod);
  }
  return 0;
}