For a given numbers x, y and n calculate

i.e. a number r such that 0 <= r < n and n | (x^y - r).

Input

t [the number of test cases <= 10]
x y n [2 <= x, n <= 2³⁰, 0 <= y <= 2³⁰ - easy (10¹⁰⁰⁰⁰ - hard)

First two test cases are easy, the following four test cases are hard. Threshold is 2 pts (the problem is accepted).

Output

r [such that x^y = r (mod n)]

Example 1 (easy)

Input:
2
54015779 489100829 472960975
827371214 966345673 443599139

Output:
350431544
391669493

Example 2 (hard)

Input:
1
29809803 47901912849872523461864631327232122 1008098565

Output:
718185534