Limits 1s, 1.0 GB

Given

find f(a, b) mod m.

Input

The first line will contain a single integer T (T <= 10), the number of test cases. Following T lines will contain 3 space-separated integers: a, b, m (1 <= a, b, m <= 10^18).

Output

Print T lines denoting the answer. Print a newline after each output.

Sample

InputOutput
1
3 2 1000
27

Submit

Login to submit.

Statistics

0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.