#### Registered Users Only

Please login to view and utilize this feature.

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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 0 | 1 | 2s | 256MB | Average |

2 | 100 | 10 | 2s | 256MB | Average |

### Judge Compile Command

g++ ans.cpp -o exponentiate -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512