# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Power and Mod

Exponentiation is a mathematical operation, written as b n , involving two numbers, the base b and the exponent n. When n is a positive integer, exponentiation corresponds to repeated multiplication of the base: that is, b n is the product of multiplying n bases:

`$ b^n = b \times ... \times b \space (n \space times) $`

In computing, the modulo operation finds the remainder after division of one number by another (sometimes called modulus). Given two positive numbers, a (the dividend) and n (the divisor), a modulo n (abbreviated as a mod n) is the remainder of the Euclidean division of a by n. For instance, the expression “5 mod 2” would evaluate to 1 because 5 divided by 2 leaves a quotient of 2 and a remainder of 1, while “9 mod 3” would evaluate to 0 because the division of 9 by 3 has a quotient of 3 and leaves a remainder of 0; there is nothing to subtract from 9 after multiplying 3 times 3.

Now, you are given the value of a, b and m. print the value of

`$ a^b \space mod \space m $`

## Input

The first line contains the number of test cases **T** (1 ≤ T ≤ 10^{4}).

The next T line contains three integers **a**, **b** (1 ≤ a, b ≤ 10^{9}) and **m** (1 ≤ m ≤ 2^{64}).

## Output

For each test case print the answer of the problem.

## Samples

Input | Output |
---|---|

2 2 3 4 3 4 5 | 0 1 |

This problem was authored for Inter Department Programming Contest 2016 at Jahangirnagar University and is being hosted on Toph per author’s request.