模拟欧拉降幂
#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <utility>
#include <cstdlib>
#include <cassert>
#include <ctime>
//#include <unordered_map>
#include <bitset>
#include <stack>
#include <sstream>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <list>
#include <set>
#include <iomanip>
#include <cctype>
#define sf scanf
#define gr getchar()
#define pf printf
#define sz(type) (type).size()
#define pb push_back
#define mp make_pair
#define IT iterator
using namespace std;
typedef long long ll;
inline ll qpow(ll,ll,ll);
const int N = 1e6+5;
int prime[N],tot;
ll phi[N],maxn = 1e6;
void pre(int n){
tot = 0;
phi[1] = 1;
memset(phi,0,sizeof(phi));
for(int i=2;i<=n;i++){
if(!phi[i]){
prime[tot++]=i;
phi[i]=1ll*(i-1);
}
for(int j=0;j<tot&&i*prime[j]<=n;j++){
if(i%prime[j]!=0) phi[i*prime[j]]=phi[i]*phi[prime[j]];
else{
phi[i*prime[j]]=1ll*prime[j]*phi[i];
break;
}
}
}
}
inline ll euler(ll n){
if(n <= 1ll*maxn) return phi[n];
ll ans = n;
for(int i=0;i<tot&&prime[i]*prime[i]<=n;i++){
if(n%prime[i]==0){
ans -= ans/prime[i];
while(n%prime[i]==0) n/=prime[i];
}
}
if(n > 1) ans -= ans/n;
return ans;
}
inline ll check(ll x,ll n,ll mod){
ll ans = 1;
for(ll i=1;i<=n;i++){
ans*=x;
if(ans >= mod) return ans;
}
return ans;
}
inline ll solve(ll a,int n,ll p){
if(n==0) return 1;
if(p==1) return 1;
ll exp = solve(a,n-1,euler(p)),ans;
ans = check(a,exp,p);
if(ans >= p) ans = qpow(a,exp,p) + p;
return ans;
}
int main(){
int t,b;
ll a,p;
pre(maxn);
sf("%d",&t);
while(t--){
sf("%lld%d%lld",&a,&b,&p);
pf("%lld\n",solve(a,b,p)%p);
}
return 0;
}
inline ll qpow(ll x,ll n,ll mod) {
ll ans = 1,a = x;
while(n) {
if(n&1) {
ans = ans*a%mod;
}
a = a*a%mod;
n>>=1;
}
return ans;
}