UVA :1230 - MODEX solution

#include <bits/stdc++.h>
#define sc scanf
#define pf printf
using namespace std;

typedef long long ll;

ll bigmod(ll base,ll pow,ll mod)
{
    if(pow==0) return 1;
    if(pow&1)
    {

        ll ret=(bigmod(base,pow-1,mod))%mod;
        return  (ret*base)%mod;

    }
    else
    {
        ll ret=(bigmod(base,pow/2,mod))%mod;
        return (ret*ret)%mod;
    }

}

int main()
{

    ll base,pow,mod;
    int n;
    while(sc("%d",&n)==1)
    {
        if(n==0) break;
        int t=n;
        while(t--)
        {
            cin>>base>>pow>>mod;
            cout<<bigmod(base,pow,mod)<<endl;
        }
    }


    return 0;
}