#include<iostream>
#include<algorithm>
using namespace std;
int quickm(int a,int k,int p)
{
    int ans=1;
    while(k){
        if(k&1)ans=(long long)ans*a%p;
        k>>=1;
        a=(long long)a*a%p;
    }
    return ans;
}
int main()
{
    int n,a,k,p;
    scanf("%d",&n);
    while(n--){
        scanf("%d%d%d",&a,&k,&p);
        printf("%d\n",quickm(a,k,p));
    }
    return 0;
}