// https://dashoj.com/p/97
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n;

int main() {
	cin >> n;
	for (ll i = 0; i < n; i++) {
		ll a, k, p, result = 1;
		cin >> a >> k >> p;
		a = a % p;
		while (k) {
			if (k % 2) result = (result * a) % p;
			k /= 2;
			a = (a * a) % p;
		}
        cout << result << endl;
	}
	return 0;
}