exponentiate_ex

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 ≤ 1,000,000).

Each of the next T lines will contain three integers A, B and M (1 ≤ A, B, M ≤ 1018).

Output

For each of the T test cases, output a single line containing one integer, the value of AB (mod M).

Sample Input 1

5
269845965585325539 410993175365329221 287854792412106895
411389931291882089 384766635564718673 573462151358502890
390854186837699009 580380201657489855 909593130690430685
146053862632939232 618473335373282330 859258565398630021
923379609753287868 721664568079866982 791491023603966291

Sample Output 1

281187621103532424
113645750044751909
535990907556162414
490196457493544167
627424821926089125

Submitting to 'exponentiate_ex'


You're not logged in! Click here to login


Submitting to 'exponentiate_ex'


You're not logged in! Click here to login


Submitting .cpp to 'exponentiate_ex'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 6 Seconds
Memory Limit: 1024MB
No. of ACs: 37
Your best score: 0
Source: Classic Problem

Subtask Score
1 0
2 100