#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef pair<int,int> aII;  
using ll = long long;
using ULL = unsigned long long;
const int N = 1e6+5;

inline ll qmi(ll a, ll b, ll p) {
    ll res = 1 % p;
    for (; b; b >>= 1) {
        if (b&1) res = res * a % p;
        a = a * a % p; 
    }
    return res;
}

inline void solve() { 
    ll a, b, p;
    cin >> a >> b >> p;
    cout << qmi(a, b, p) << endl;
}
int main() { 
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //int _ = 1; 
    int _; cin >> _;
    while (_--) solve();
    return 0;
}