K 次剩余（模意义下的 K 次方根）

时间限制：5 秒

题目描述

每个测试包含 $T$ 组数据。

给定 $K, Y, P$（$P$ 为质数）。

输出任意一个满足 $X^K \equiv Y \pmod P$ 的 $X$；若不存在这样的 $X$，则输出 $-1$。

注意，在本题中约定 $0^0 \equiv 1 \pmod P$。

约束条件

• $1 \le T \le 5000$
• $0 \le K \le 10^9$
• $2 \le P \le 10^9$
• $0 \le Y < P$
• $P$ 是质数。

输入

T
K_0 Y_0 P_0
K_1 Y_1 P_1
⋮
K_{T-1} Y_{T-1} P_{T-1}

输出

对于每一行，输出 $X$ 或 $-1$。

5
0 10 11
10 9 11
1 1 2
5 4 13
0 8 11

-1
-1
1
10
-1