MODPOW - Calculating very big numbers very quickly

no tags 

Given numbers A, B, C, calculate (A to the power of B) mod C.

Input

The first line will contain an integer x, the number of test cases. x lines follow, each with three integers A, B, and C, the A, B, and C mentioned above.

Conditions:

A is no more than 1e5

B is no more than 1e18

C is no more than 1e7

Output

For each test case, print (A^B) mod C.

Example

Input:
1
1 1 2

Output: 1

hide comments
hendrik: 2011-09-13 19:22:14

yet another a^b%c. There are too many of them. See for example FASTPOW.


Added by:hua
Date:2011-09-12
Time limit:1.465s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Alex Anderson