#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;

int n;
int a,b,p;

int qpow()
{
    ll base=a%p;
    ll ret=1;
    while(b)
    {
        if(b&1) ret=(ret*base)%p;
        b>>=1;
        base=(base*base)%p;
    }
    return ret;
}

int main()
{
    cin>>n;
    while(n--)
    {
        scanf("%d%d%d",&a,&b,&p);
        printf("%d\n",qpow());
    }
    return 0;
}