問題文

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

入力

$T$
$p_1$ $k_1$ $a_1$
$p_2$ $k_2$ $a_2$
$⋮$
$p_T$ $k_T$ $a_T$

$T$個のテストケースが与えられる。 $i$番目のテストケースに対して $x^{k_i}\equiv a_{i}mod{p}_i$ の解を一つ出力せよ。解が存在しなければ$-1$を出力せよ。
$1\le T\le 1000$
$1\le k_i\le 1000$
$2\le p_i\le {10}^9+7$
$1\le a_i<p_i$

問題公開後、アルゴリズムの高速化に成功したため
$1\le T\le 1000$
$1\le k_i\le {10}^9$
$2\le p_i\le {10}^{18}$
$1\le a_i<p_i$
のテストケースが追加されました(2020/02/10)。evilケースとして追加されているのでステータスに影響はしません。

更に以下のケースがevil_hardとして追加されました(2020/02/13)。
$1\le T\le 1000$
$1\le k_i<p$
$2\le p_i\le {10}^{18}$
$1\le a_i<p_i$

出力

$x^{k_i}\equiv a_{i}mod{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