#include <bits/stdc++.h>

using namespace std;

long long a ,k ,p;
//mypow 只是一个自定义名字
long long myPow( long long a , long long k , long long p) {
long long res=1;
while (k){
	if(k&1)
	res=res*a%p;
	k >>=1;/相当于指数除以2
	a = a*a%p;
}
return res;
}
        


int main(){

int n;
cin >>n;
while (n--) {
	long long a,k ,p;
	cin >>a>>k >>p;
	cout << myPow(a,k,p) << '\n';
}


return 0;

}