本题考察快速幂算法和快速乘算法，快速幂算法可以正着进行也可以反着进行，在这里采用正着进行倍增的思路。
以2^10为例，其中指数10可以变成二进制1010，也就可以变成2^(2^3)+2^(2^1)。2的出现也就意味着可以使用倍增的思路去求解。
也就是将指数变成二进制进行挨个计算，在计算过程中维护temp的倍增。这样如果当前二进制位等于1的时候可以直接乘于temp。
另外在本题当中由于在相乘的过程中会超出long long的范围，所以还需要使用快速乘算法，将乘法变成多个加法。使用递归去实现。
代码： 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll fast_multiply(ll a, ll b, ll p) {
    if (b==0) {
        return 0;
    }
    if (b==1) {
        return a%p;
    }
    ll ans = 0;
    if (b&1) {
        ans = (ans%p+a%p)%p;
        b--;
    }
    ll num = fast_multiply(a, b/2, p);
    ans = (ans%p+num%p+num%p)%p;
    return ans;
}

ll fast_mi(ll a, ll b, ll p) {
    ll temp = a;
    ll ans = 1;
    while (b) {
        if (b&1) ans = fast_multiply(ans, temp, p);
        temp = fast_multiply(temp, temp, p);
        b = (b>>1);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    ll a,b,p;
    while (T--) {
        cin>>a>>b>>p;
        cout<<fast_mi(a, b, p)<<endl;
    }
    return 0;
}