Given an integer A, N and M, calculate R = A^N modulo M, ie. the remainder after dividing N-th power of A by the modulus M.

Input

First line: positive integer T - numer of test cases, T<1000.
Next T lines contain 3 integers each: A_i, N_i and M_i.
Data constraints:
-2³⁰ < A_i < +2³⁰
0 < N_i < +2⁶⁰
2 < M_i < +2³⁰

Output

For each of test cases, output the number R_i - one in each line.

Example

Input:
6
1 2 3
4 5 6
7 8 9
12 34 56
78 90 123
4567890 123456789012 34567890


Output:
1
4
4
16
42
781950