#include<iostream>
using namespace std;
typedef long long LL;LL qmi(int a,int b,int p){LL res=1%p;//%p是为了p=1的时候,余数是0while(b){if(b&1) res=res*a%p;//位数是1的b>>=1;a=a*(LL)a%p;//a*a再modp是为了防止溢出}return res;
}int main(){int n;cin>>n;while(n--){int a,b,p;cin>>a>>b>>p;printf("%lld\n",qmi(a,b,p));}return 0;
}