K번째 근 (모듈러)

각 테스트 케이스는 $T$개의 케이스로 구성된다.

$K, Y, P(P: \textrm{prime})$이 주어진다.

$X^K \equiv Y \pmod{P}$을 만족하는 임의의 $X$을 출력하거나, 그러한 $X$이 없다면 $-1$을 출력한다.

이 문제에서는 $0^0\equiv 1 \pmod{P}$임에 유의한다.

제약 조건

• $1 \leq T \leq 5000$
• $0 \leq K \leq 1000000000$
• $2 \leq P \leq 1000000000$
• $0 \leq Y < P$
• $P$은 소수이다.

$T$
$K_0$ $Y_0$ $P_0$
$K_1$ $Y_1$ $P_1$
$\vdots$
$K_{T-1}$ $Y_{T-1}$ $P_{T-1}$

각 줄에 $X$ 또는 $-1$을 출력한다.