#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    while(n--){
        long long  a,b,p,ans=1;
        cin>>a>>b>>p;
        while(b!=0)
        {
            if(b&1) ans=ans*a%p;
            b>>=1;
            a=a*a%p;
        }
        cout<<ans<<endl;
    }
}