#include <iostream>

using namespace std;
int qmi(int a,int b,int p){
    int res=1%p;
    while(b){
        if(b&1) res=(long long)res*a%p;//防止溢出
        b=b>>1;
        a=(long long)a*a%p;
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    while(n--){
        int a,b,p;
        cin>>a>>b>>p;
        cout<<qmi(a,b,p)<<endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}