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 A^B (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 ≤ 10¹⁸).

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

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

Sample Output 1

281187621103532424
113645750044751909
535990907556162414
490196457493544167
627424821926089125