모듈러 제곱근

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

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

$X^2 \equiv Y (\bmod P)$을 만족하는 $X$를 출력하고, 그러한 $X$가 없으면 $-1$를 출력한다.

제약 조건

• $1 \leq T \leq 100,000$
• $2 \leq P \leq 10^9$
• $0 \leq Y < P$
• $P$은 소수이다.

$T$
$Y_0$ $P_0$
$Y_1$ $P_1$
:
$Y_{T-1}$ $P_{T-1}$

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