#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n;
ll Mi[40];



ll quick_M(ll a, ll b, ll p)
{
    // 初始化答案为1
    ll res = 1;
    
    // 将b用二进制表示
    while(b)
    {
        // 如果二进制位为1，则相乘（如上图右半边）
        if(b & 1) res = res * a % p;
        b >>= 1;
        
        // 每个数是上一个数的平方（如上图的左半边）
        // 即使中间某个二进制位是0也不跳过平方这一步骤
        a = a * a % p;
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin>>n;
    
    ll a, b, p;
    while(n--)
    {
        cin>>a>>b>>p;
        cout<<quick_M(a, b, p)<<'\n';
    }
    
    return 0;
}