模意义下开平方

【题目描述】

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

给定 $Y, P(P: \textrm{质数})$。

输出满足 $X^2 \equiv Y (\bmod P)$ 的 $X$；如果不存在这样的 $X$，则输出 $-1$。

【输入】

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

【输出】

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

【输入样例】

5
0 5
1 5
2 5
3 5
4 5

【输出样例】

0
1
-1
-1
2

【数据范围】

• $1 \leq T \leq 100,000$
• $2 \leq P \leq 10^9$
• $0 \leq Y < P$
• $P$ 是质数。

【来源】

Library Checker（yosupo06） sqrt_mod

本题为 special judge（输出任意合法解），暂不可本地评测。