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*).

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).

For each of the *T* test cases, output a single line containing one integer, the value of *A ^{B}* (mod

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

25 1 24 1024

Subtask | Score |
---|---|

1 | 100 |

2 | 0 |