#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

//求a^k % p的快速幂函数
int qmi(int a, int k,int p)
{
    int res = 1;
    while(k)
    {
        if(k&1) res = (LL)res*a % p;
        k >>= 1;
        a = (LL)a*a %p;
    }
    return res;
}


int main()
{
    //输入
    int n;
    scanf("%d",&n);

	//调用函数+输出
    while(n--)
    {
        int a,k,p;
        scanf("%d%d%d",&a,&k,&p);

        printf("%d\n",qmi(a,k,p));

    }
    return 0;
}