P5491 【模板】二次剩余

题目描述

给出 $N,p$,求解方程 $$ x^2 \equiv N \pmod{p} $$ 多组数据,**且保证 $p$ 是奇素数。**

输入格式

第 $1$ 行,一个整数 $T$ 表示数据组数。 第 $2\sim T+1$ 行,每行两个整数 $N$ 和 $p$,含义详见题目描述。

输出格式

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

说明/提示

对于 $100\%$ 的数据,$1\leq T\leq 10^4$,$0\le N, p\leq 10^9+9$。