/*
I n : ai, bi, pi 
计算快速幂 : a ^ b mod p
O 快速幂

I 
2
3 2 5
4 3 9

O
4
1
*/

#include <iostream>
#include <algorithm>

using namespace std;

// 数论计算过程中可能会超过int
typedef long long LL;

// 快速幂
LL qmi(int a, int b, int p)
{
    // 初始化
    LL res = 1 % p;
    while (b)
    {
        if (b & 1) res = res * a % p;
        // 分解幂形式 a ^ (c0 * 2^0 + c1 * 2^1 + ... + cn * 2^n)
        a = a * (LL)a % p;
        // 每轮更新一位，且从b的小位开始更新
        b >>= 1;
    }
    return res;
}


int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        printf("%lld\n", qmi(a, b, p));
    }

    return 0;
}