It is a sunny day, and qualifications for level 4 are running in AAST.

The contestants hacked the server and was able to get a file that contain solutions to all problems, but unfortunately the file was encrypted.

They know that the decryption key is in form of (a ^ b) % m (a raised to power b modulo m), and they know a, b and m but they don't know the result of this equation and asked you for help.

Input

First line contains single integer T, then T lines follow, each line contains three integers: a, b, m.

Output

You should print T lines, which is the output of above equation.

Constraints

1 <= T <= 1000

0 <= a <= 1000000000000000000

0 <= b <= 1000000000000000000

1 <= a + b

1 <= m <= 1000000000000000000

Example

Input:
1
2 3 5

Output:
3

Explanation

(2^3)%5 = 8%5 = 3