#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
int main()
{
int n;
cin >> n;
while (n -- )
{
int a , b , p , ans = 1;
cin >> a >> b >> p;
while (b)
{
if (b & 1)
{
ans = (LL)ans * a % p;
}
a = (LL)a * a % p;
b >>= 1;
}
cout << ans % p << endl;
}
return 0;
}