#include<iostream>using namespace std;int main(){__int64 a,b,c,mod,n;cin>>n;while(n--){cin>>a>>b>>c;if(c==1)mod=0;elseif(b==0&&c>1)mod=1;else{mod=1;while(b--){mod*=a;mod%=c;}}cout<<mod<<endl;}}