#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int x,y;
long long int p;
scanf("%d\n",&x);
scanf("%d\n",&y);
scanf("%ld\n",&p);
long long int sum;
for(int i=0;i<y;i++){
sum*=x;
}
printf("%ld\n",fmod(sum,p)) ;
}
}