Problem Statement

Let $p$ be a prime. Find one solution of $x^k \equiv a \bmod p$. If no solution exists, output $-1$.

Input

$T$
$p_1$ $k_1$ $a_1$
$p_2$ $k_2$ $a_2$
$\vdots$
$p_T$ $k_T$ $a_T$

You are given $T$ test cases. For the $i$-th test case, output one solution of $x^{k_i} \equiv a_i \bmod p_i$. If no solution exists, output $-1$.
$1 \leq T \leq 1000$
$1 \leq k_i \leq 1000$
$2\leq p_i\leq 10^9+7$
$1 \leq a_i < p_i$

After the problem was published, the algorithm was successfully sped up, so
$1 \leq T \leq 1000$
$1 \leq k_i \leq 10^9$
$2\leq p_i\leq 10^{18}$
$1 \leq a_i < p_i$
test cases with these constraints were added (2020/02/10). They were added as evil cases, so they do not affect the status.

In addition, the following cases were added as evil_hard (2020/02/13).
$1 \leq T \leq 1000$
$1 \leq k_i < p$
$2\leq p_i\leq 10^{18}$
$1 \leq a_i < p_i$

Output

Output a solution of $x^{k_i} \equiv a_i \bmod p_i$ on each line. However, if no solution exists, output $-1$. Print a newline at the end.

Sample

1
13 2 4

11

1
3 2 2

-1

10
23 6 19
19 9 14
23 10 7
31 7 25
29 6 20
19 7 14
19 7 12
31 2 5
19 8 9
29 9 11

-1
-1
-1
25
16
2
12
25
17
19