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