【模板】二次剩余

题目背景

模板题,无背景。

题目描述

给出 $N,p$,求解方程 $$ x^2 \equiv N(\bmod ~p) $$ 多组数据。 **保证 $p$ 是奇素数。**

输入输出格式

输入格式


第一行一个整数 $T$ 表示数据组数。 接下来 $T$ 行,每行两个整数,分别是 $N$ 和 $p$ 。

输出格式


输出共 $T$ 行。 对于每一行输出: 若有解,则按 $\bmod ~p$ 后递增的顺序输出在 $\bmod~ p$ 意义下的全部解。 若两解相同,只输出其中一个。 若无解,则输出 `Hola!` 。

输入输出样例

输入样例 #1

3
5 1000000009
4 1000000009
0 19260817

输出样例 #1

383008016 616991993
2 1000000007
0

说明

$1\leq T\leq 10000$ $1\le N, p\leq 10^9+9$