模意义下的平方根 (Sqrt Mod)

时间限制：10 秒

题目描述

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

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

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

约束条件

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

输入

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