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 .cpp to 'Exponentiate'


You're not logged in! Click here to login


Compile Errors


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

Subtask Score
1 100
2 0