/*
思路：
    思路一：
       1 (a.b)%c = ((a%c)*(b%c))%c
       2 pow(3,10)=pow(pow(3,2),5)=pow(9*3,4)=pow(pow(27,2),2)


*/

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll function_Modexpfast ( ll a , ll b , ll c ) {
    a = a % c;
    ll result = 1; //记录a的b次方
    while ( b != 0 ) { //循环操作 b&1
        if ( b % 2 == 1 ) { // 每次对b除以2 奇数时则是result记录时。
            result = (result * a) % c; //奇数时 a的b次方= a*a * a的b－1次方 
        }
        a = (a * a) % c;
        b = b >> 1; //向右移动一位 就是除以2

    }
    cout << result << endl;
    return result;
}

int main()
{
    int n;
    cin >> n;
    for ( int i = 1; i <= n; i++ ) {
        ll a, b, c;
        cin >> a >> b >> c;
        function_Modexpfast(a , b , c);
    }
      

    return 0;
}