uva 1230

#include<stdio.h>
#include<math.h>
long long bigmod(long long b,long long p,long long m)
{
    long long c;
    if(p==0)
        return 1;
    if(p%2==1)
    {
        return ((b%m)*(bigmod(b,p-1,m)))%m;

    }
    else
    {
        c =  bigmod(b ,p / 2, m);
        return (c * c) % m;
    }
}


int main()
{
    long long t, i,j,k,a,d,e;
    while(scanf("%lld",&t)==1)
    {
        if(t==0)
            break;
        for(i=1;i<=t;i++)
        {

            scanf("%lld %lld %lld",&a,&d,&e);
            //k=bigmod(a,d,e);

            printf("%lld\n",bigmod(a,d,e));

        }
    }
    return 0;
}