MODEX

#include<bits/stdc++.h>

using namespace std;

int Big_Mod(int base,int power,int mod)
{
    int a,b;

    if(power==0)
    {
        return 1;
    }
    else if(power%2==1)
    {
        a = base%mod;

        b = (Big_Mod(base,power-1,mod))%mod;

        return (a*b)%mod;
    }
    else if(power%2==0)
    {
        a=(Big_Mod(base,power/2,mod))%mod;

        return (a*a)%mod;
    }
}

int main()
{
    int i,a,base,power,mod,test;

    while(scanf("%d",&test)&&test)
    {
        for(i=1; i<=test; i++)
        {
            scanf("%d%d%d",&base,&power,&mod);

            a = Big_Mod(base,power,mod);

            printf("%d\n",a);
        }
    }

    return 0;
}