Mod of Power

/*
    Task    : Mod Of Power
    Author  : Phumipat C. [MAGCARI]
    Language: C++
    Created : 30 July 2022 [11:03]
*/
#include<bits/stdc++.h>
using namespace std;
int mod(int a,int b,int c){
    //base case
    if(b == 1)  return a%c;
    //process
    int res = mod(a,b/2,c);
    if(b%2 == 0)
        return (res*res)%c;
    else
        return (((res * res) % c) * a) % c;
}
int main(){
    int q,a,b,c;
    cin >> q;
    while(q--){
        cin >> a >> b >> c;
        cout << mod(a,b,c) << '\n';
    }
    return 0;
}