#include<iostream>
using namespace std;

typedef long long LL;
LL quickPow(LL a, LL b, LL p)  {
    LL res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main () {
    int n, a, b, p;
    cin >> n;
    while (n -- ) {
        cin >> a >> b >> p;
        cout << quickPow(a, b, p) << endl;
    }
}