Problem description:

Faizaan and Sejal were playing Mathematics games. Faizaan gave Sejal three numbers: N, M and K. Sejal has to find out a number X such that
X = (N^M)%K
Sejal initially thought that the problem was very easy, but she soon realised that N and M were very huge numbers. Help Sejal find out X.
Note: A^B represents the value A raised to the power B.

Input:
First line contains a single integer 'T', denoting the number of test cases.
There are three lines of input for every test case.
First line contains single integer N
Second line contains single integer M
Third line contains single integer K

Output:
Answer for all 'T' test cases in 'T' lines.

Constraints:
1 <= T <= 10
1 <= N <= 10^100000
1 <= M <= 10^200
1 <= K <= 10^9

Sample Input:
1
3
4
5

Sample Output:
1

见题面

见题面