由于数据比较大，所以我们不可能直接求。

我们可以考虑把拆分成其对应的二进制形式，然后进行求解。

比如说：a = 4， b = 5

那么b的二进制形式就是： 0101

那么4^5 = 4^(2^2+2^0) = 4^2^2 * 4^2^0

由于二进制中相邻两位存在2倍关系，不管b的最后一位是否为1，a都要平方，如果b的最后一位是1，那么结果就乘上a，如果是0，那么就不乘。

模板：

#include <iostream>
using namespace std;
typedef long long LL;
int  n;

LL qmi(int a, int k, int p)
{
    LL res = 1;
    while(k)
    {
        if(k&1) res = (res * a) % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    
    return res;
}
int main()
{
    cin >> n;
    while(n--)
    {
        int a, k, p;
        cin >> a >> k >> p;
        cout << qmi(a, k, p) << endl;
    }
    
    return 0;
}