#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

//快速幂

//将B化成二进制,如5的11次方,11的二进制为1011

//将B的二进制中为1的位置对应的A的2的k次幂相乘,得到最终结果。

int quickpow(LL a,LL n,LL p)

{

LL ans = 1;
for(; n ;n >>= 1)
{
	if(n & 1)
		ans *= a,ans %= p;
		a *= a;
		a %= p; 
}
return ans;

}

int main() {

int T;
cin >> T;
while(T--)
{
    LL A,B,P;
    cin >> A >> B >> P;
    cout << quickpow(A,B,P) << endl;
}

}