505032 - 二次剩余

【题目描述】二次剩余(qr)

给出N和p(保证p是奇素数),求解方程x2≡N(mod p)。

输入

第1行一个整数T(1≤T≤10^4)表示数据组数。 第2∼T+1行,每行两个整数N和p(0≤N,p≤10^9 +9)。

输出

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

样例

输入

3
5 1000000009
4 1000000009
0 19260817

输出

383008016 616991993
2 1000000007
0
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题