Exponentiate

This question consists of T test cases. Each test case consists of three integers A, B and M. For each test case, we wish to know the value of A^B (mod M).

Input

The first line will contain one integer T (1 ≤ T ≤ 100,000).

Each of the next T lines will contain three integers A, B and M (1 ≤ A, B, M ≤ 1,000,000).

Output

For each of the T test cases, output a single line containing one integer, the value of A^B (mod M).

Sample Input 1

4
5 2 100
5 2 24
2 10 1000
2 10 10000

Sample Output 1

25
1
24
1024