問題文

$p$を素数とする。$x^k \equiv a \bmod p$ の解を一つ求めよ。解が存在しなければ$-1$を出力せよ。

入力

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

$T$個のテストケースが与えられる。 $i$番目のテストケースに対して $x^{k_i} \equiv a_i \bmod p_i$ の解を一つ出力せよ。解が存在しなければ$-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$

問題公開後、アルゴリズムの高速化に成功したため
$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$
のテストケースが追加されました(2020/02/10)。evilケースとして追加されているのでステータスに影響はしません。

更に以下のケースが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$

出力

$x^{k_i} \equiv a_i \bmod p_i$ の解を各行に出力してください。 ただし、解が存在しなければ$-1$を出力してください。 最後に改行してください。

サンプル

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