Russian Peasunt Theorem

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

///pre-processing
#define     gcd(a, b)       __gcd(a,b)
#define     lcm(a, b)       (a * b) / gcd(a, b)
#define     loop(i, n)      for(int i=0;i<n;i++)
#define     all(x)          x.begin(),x.end()
#define     mem(a, x)       memset(a,x,sizeof a)
#define     endl            '\n'
#define     ss              second
#define     ff              first
#define     TN              typename

///input functions
int Int(){int x;scanf("%d",&x);return x;}
long long Long(){long long x;scanf("%lld",&x);return x;}
double Double(){double x;scanf("%lf",&x);return x;}

///input functions shorting
#define Int Int()
#define Long Long()
#define Double Double()
#define Float Float()
const int N = (int) 1e5 + 5;
unsigned long long peasant(unsigned long long a, unsigned long long b, unsigned long long MOD){
    unsigned long long res = 0;
    while(b){
        if(b & 1){res += (a % MOD), res %= MOD;}
        a <<= 1;
        a %= MOD;
        b >>= 1;
    }
    return res;
}
unsigned long long bigMod (unsigned long long base, unsigned long long power, unsigned long long MOD){
    long long res = 1;
    while (power){
        if (power & 1){
            res = peasant(res, base, MOD) % MOD;
        }
        base = peasant(base, base, MOD) % MOD;
        power = power >> 1;
    }
    return res;
}
int main()
{
    int t, cs = 0;
    cin>>t;
    while(t--){
       /// printf("Case %d: ", ++cs);
        unsigned long long a, b, c;
        cin >> a >> b >> c;
        cout << bigMod(a, b, c) <<endl;
    }
    return 0;
}