ncc3_28515
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
t = int(raw_input())
for i in range(t) :
    n = int(raw_input())
    m = int(raw_input())
    k = int(raw_input())
    print pow(n,m,k)
1
3
4
5 1
2
4
5 1
2
4
7 1
2
4
2 1
2
5
7 1
2
3
5 1
-1
1
8 1
-2
1
8 1
5
1
7 1
-2
1
12 1
-3
1
12 1
-2
4
22 1
-1
2
-3 1
-2
1
22 1
-1
19
13 1
1
2
-4 1
2
1
-3 1
2
0
-5 1
2
0
-7 1
0
0
-8 1
0
0
-15 1
8
1
21 1
-1
7
22 1
-1
7
38 1
-1
9
73 1
-1
1
23 1
-1
1
12 1
-1
1
19 1
5
2
109 1
-2
7
41 1
-1
9
20 1
-1
1
14 1
-2
6
50 1
-1
1
31 1
-1
1
32 1
-1
1
43 1
-1
1
123 1
-1
1
75 1
-2
1
123 1
-1
1
61 1
-1
3
196 1
-1
7
90 1
-2
1
198 1
-2
3
196 1
-1
7
162 1
-1
3
341 1
9
2
170 1
-1
1
598 1
-1
5
76 1
-2
3
34 1
-1
17
18 1
-1
5
118 1
-6
1
233 1
2
11
162 1
3
3
98 1
-1
1
36 1
2
11
95 1
-6
3
64 1
-1
1
376 1
2
4
3 1
1
4
3 1
3
4
2 1
3
8
2 1
1
8
2 1
2
8
2 1
2
8
4 1
2
5
4 1
2
3
7 1
2
3
4 1
4
3
4 1
4
3
3 1
2
3
3 1
2
1
3 1
2
1
4 1
2
0
4 1
0
0
4 1
0
1
4 1
0
1
5 1
0
1
2 1
0
1
1 1
0
0
1 1
0
0
2 1
1
1
2 1
1
1
1 1
-1
1
2 1
-1
0
2 1
-1
0
1 1
-1
1
1 1
-2
1
1 1
-2
0
1 1
-2
2
1 1
-2
2
2 1
-2
4
2 1
-2
3
2 1
-1
3
2 1
-2
0
2 1
3
4
9 1
3
4
4 1
3
4
7 1
2
2
3 1
1
4
4
1 1
 2
 0
 4
 3
 7
 6
 5
 10
 9
 16
 -2
 20
 12
 -3
 -1
 -4
 -6
 -7
 -14
 8
 21
 37
 72
 22
 11
 18
 25
 36
 19
 13
 14
 30
 31
 42
 122
 74
 121
 60
 195
 89
 196
 188
 161
 340
 81
 597
 75
 26
 17
 117
 227
 104
 27
 35
 53
 40
 375
 1
 1
 1
 1
 1
 0
 0
 0
 1
 0
 0
 1
 2
 2
 2
 1
 1
 0
 0
 0
 0
 0
 1
 1
 0
 1
 1
 0
 0
 0
 0
 0
 0
 0
 0
 1
 1
 0
 1
 4
 1
 1
