#include<iostream>
#include<string>
#include<cstdio>
#define ll long long
using namespace std;
ll pow_mod(ll a,ll b,ll mod){
    ll ans = 1;
    a %= mod;
    while(b){
        if(b&1){
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main()
{
    int t;
    ll a,b,n;
    scanf("%d",&t);
    while(t--){
        scanf("%lld %lld %lld",&a,&n,&b);
        printf("%lld\n",pow_mod(a,n,b));
    }
    return 0;
}