重铸华农荣光 我辈义不容辞

The twentieth day - quick power

#include<iostream>
using namespace std;

typedef long long ll;

void solve(ll a,ll k,ll p)
{
    ll ans=1%p;
    while(k)
    {
        if(k&1) ans=ans*a%p;
        k>>=1;
        a=a*a%p;
    }
    cout<<ans<<endl;
}
int main()
{
    ll n;
    cin>>n;
    while(n--){
        ll a,k,p;
        cin>>a>>k>>p;
        solve(a,k,p);
    }
    return 0;
}