数论中模的运算：

a*b%n=(a%n)*(b%n)%c;

(a+b)%n=(a%n+b%n)%n;

幂的模：A^n%c=r    于是A^(n+1)%c=A*r%c;

#include<iostream>

using namespace std;

int main()

{

int T,i;

_int64 a, b, c, r; //定义64位整数，避免后面中间结果溢出

cin >> T;

while (T--)

{

cin >> a >> b >> c;

r = a%c;

for (i =1; i < b; i++)

r =a*r%c;

cout << r << endl;

}

return 0;

}