Bigmod in iteraive way (1 <= A, B <= 1000000000000000000, 1 < M < 1000000000).

#include<bits/stdc++.h>
using namespace std;


long long Power(long long BaSe,long long PoWeR,long long MoD){
    //if BaSe zero
    BaSe%=MoD;
    long long ret=1;
    while(PoWeR>0){
        if(PoWeR&1) ret=(ret*BaSe)%MoD;
        PoWeR>>=1;
        BaSe=(BaSe*BaSe)%MoD;
    }
    if(ret==0) return MoD;
    return ret;
}


main(){
    int Case;
    scanf("%d",&Case);
    while(Case--){
        long long a,b,m;
        scanf("%lld %lld %lld",&a,&b,&m);
        printf("%lld\n",Power(a,b,m));
    }
    return 0;
}