#include<bits/stdc++.h>
#define ll long long
using namespace std;
int qmi(int a,int b,int p){
    int ans=1;
    while(b){
        if(b&1) ans=(long long)ans*a%p;
        b>>=1;
        a=(long long)a*a%p;
    }
    return ans;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int a,b,p;
        cin>>a>>b>>p;
        auto ans=qmi(a,b,p);
        printf("%d\n",ans);
    }
}