Binary pow

#include <iostream>
#define int long long
using namespace std;

/*int pow(int a, int b, int M) {
    if (b == 0) {
        return 1 % M;
    }
    if (b % 2 == 1) {
        return pow(a, b - 1, M) * a % M;
    } else {
        int ak = pow(a, b / 2, M);
        return ak * ak % M;
    }
}*/

int pow(int a, int b, int M) {
    int res = 1 % M;
    while (b != 0)
        if (b % 2 == 1) {
            res *= a;
            res %= M;
            b--;
        }
        else {
            a *= a;
            a %= M;
            b /= 2;
        }
    return res;
}

signed main()
{
    int t;
    cin >> t;
    while (t--) {
        int a, b, M;
        cin >> a >> b >> M;
        cout << pow(a, b, M) << "\n";
    }
    return 0;
}