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 AB (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 AB (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

Submitting to 'Exponentiate'


You're not logged in! Click here to login


Submitting to 'Exponentiate'


You're not logged in! Click here to login


Submitting .cpp to 'Exponentiate'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 2 Seconds
Memory Limit: 256MB
No. of ACs: 216
Your best score: 0
Source: Classic Problem

Subtask Score
1 100
2 0