学步园

#include<iostream>
using namespace std;
int main()
{
    __int64 a,b,c,mod,n;
    cin>>n;
    while(n--)
    {
        cin>>a>>b>>c;
        if(c==1)
        mod=0;
        else
        if(b==0&&c>1)
        mod=1;
        else
        {
            mod=1;
            while(b--)
            {
                mod*=a;
                mod%=c;
            }
        }

        cout<<mod<<endl;
    }
}