#include<bits/stdc++.h>
#define i128 __int128
using namespace std;
template <typename T> inline void read(T &x) {
    x = 0; char ch = getchar();int f=1;
    while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x*=f;
}
int T,x,y;
i128 mod;
inline void add(i128 &x,i128 y){x+=y;if(x>=mod)x-=mod;}
inline i128 Mul(i128 x,i128 y){
	i128 ans=0;
	for(;y;y>>=1){
		if(y&1) add(ans,x);
		add(x,x);
	}
	return ans;
}
inline i128 Pw(__int128 x,int y){
	__int128 ans=1;
	for(;y;y>>=1){
		if(y&1) ans=Mul(ans,x);
		x=Mul(x,x);
	}
	return ans;
}
void print(i128 x){
	if(x>9) print(x/10);
	putchar(48+x%10);
}
int main(){
	read(T);
	while(T--){
		read(x),read(y),read(mod);
		print(Pw(x,y));
		putchar('\n');
	}
	return 0;
}