// 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;
}

def quick_pow_mod_iterative(a, b, p):
    result = 1
    base = a % p
    while b > 0:
        if b % 2 == 1:  # b 是奇数
            result = (result * base) % p
        base = (base * base) % p
        b //= 2
    return result

n = int(input())
for _ in range(n):
    a, k, p = map(int, input().split())
    result = quick_pow_mod_iterative(a, k, p)
    print(result)

#include <bits/stdc++.h>

using namespace std;

long long a ,k ,p;
//mypow 只是一个自定义名字
long long myPow( long long a , long long k , long long p) {
long long res=1;
while (k){
	if(k&1)
	res=res*a%p;
	k >>=1;/相当于指数除以2
	a = a*a%p;
}
return res;
}
        


int main(){

int n;
cin >>n;
while (n--) {
	long long a,k ,p;
	cin >>a>>k >>p;
	cout << myPow(a,k,p) << '\n';
}


return 0;

}

拓展: 如果 $k$ 可以为负数, 即 $a^{-|k|}$ (这样写是为了方便看(因为严格来讲k现在是负数)) 那么可以先求 $a^{|k|}$ 然后 返回 $1/a^{|k|}$ (注: 返回值为double), 特判 k 为负数的情况. (可以试试力扣pow(x, y)这题)❤️

#include <iostream>
using namespace std;

using ll = long long;

ll myPow(ll a, ll k, ll p) {
	ll res = 1;
	while (k) {
		if (k & 1)
			res = res * a % p;
		k >>= 1;
		a = a * a % p;
	}
	return res;
}

int main() {
	int n;
	cin >> n;
	while (n--) {
		ll a, k, p;
		cin >> a >> k >> p;
		cout << myPow(a, k, p) << '\n';
	}
	return 0;
}