8994: [yosupo] Number Theory - Sqrt Mod
[Creator : ]
Description
Each test cases consists of $T$ cases.
Given $Y, P(P: \textrm{prime})$.
Print $X$ s.t. $X^2 \equiv Y (\bmod P)$, or $-1$ if there is no such $X$.
Given $Y, P(P: \textrm{prime})$.
Print $X$ s.t. $X^2 \equiv Y (\bmod P)$, or $-1$ if there is no such $X$.
Input
$T$
$Y_0$ $P_0$
$Y_1$ $P_1$
:
$Y_{T-1}$ $P_{T-1}$
$Y_0$ $P_0$
$Y_1$ $P_1$
:
$Y_{T-1}$ $P_{T-1}$
Output
For each line, print $X$ or $-1$.
Constraints
$1 \leq T \leq 100,000$
$2 \leq P \leq 10^9$
$0 \leq Y < P$
$P$ is prime
$2 \leq P \leq 10^9$
$0 \leq Y < P$
$P$ is prime
Sample 1 Input
5
0 5
1 5
2 5
3 5
4 5
Sample 1 Output
0
1
-1
-1
2