Modular Exponentiation

Given three integers A, B, and M, your task is to compute \(A^B \bmod M\). In other words, you need to calculate the remainder when \(A^B\) is divided by M. This problem requires an efficient solution using fast modular exponentiation (also known as exponentiation by squaring) to handle very large values of A and B.

Note: If M equals 1, the result should be 0 since any number modulo 1 is 0.

inputFormat

The input begins with an integer T, representing the number of test cases. Each of the next T lines contains three space-separated integers: A, B, and M.

For example:

7
2 3 5
10 5 100
123456789 987654321 1000000007
1 123456789 1000000007
123456789 1 1000000007
5 3 1
123456789 0 1000000007

outputFormat

For each test case, output a single integer representing \(A^B \bmod M\) on a new line.

For the sample input above, the output should be:

3
0
652541198
1
123456789
0
1

## sample

2
2 3 5
10 5 100

3
0

</p>