#include<bits/stdc++.h>
using namespace std;
long long n,a,b,c,sum;
int main()
{
    cin>>n;
    for(long long i=1;i<=n;i++)
    {
        long long z,j=1;
        sum=1;
        cin>>a>>b>>c;
        z=a;
        while(b!=0)
        {
            while(b%(j*2)!=0)
            {
                b-=j;
                sum*=z;
                sum%=c;
            }
            j=j*2;
            z=z*z%c;
        }
        cout<<sum<<endl;
    }
    return 0;
}