/(/text{Summary}/)

实际上是做法的归纳
一切皆是结论性的，没有证明！

模 /(p/) 意义下的二次剩余有 /(/frac{p-1}2/) 个，二次非剩余也恰有那么多

考虑解关于 /(x/) 的同余方程

/[x^2 /equiv n /pmod p
/]

当 /(n=0/) 时，/(x=0/) 是唯一解
当 /(n /not= 0/) 时，若方程有解，则只有两个互为相反数的解
判断有无解：欧拉准则
考虑 /(n^{/frac{p-1}{2}}/) 模 /(p/) 的结果
由 /((n^{/frac{p-1}{2}})^2 /equiv 1 /pmod p/)
只其结果只为 /(1/) 或 /(-1/)
/(1/) 时有解，/(-1/) 时无解

求解的话，先随机找到一个 /(a/) 满足 /(a^2 – n/) 为二次非剩余，令 /(i^2 = a^2 – n /equiv -1 /pmod p/)
类似实部和虚部，定义这个 /(i/)
有

/[(a+i)^{p+1} /equiv n /pmod p
/]

证明的话，有
/(/text{Lemma 1}/)

/[i^p /equiv -i /pmod p
/]

/(/text{Lemma 2}/)

/[(x+y)^p /equiv x^p+y^p /pmod p
/]

然后

/[/begin{aligned}
(a+i)^{p+1} & /equiv (a+i)^p(a+i) //
&/equiv (a+i)(a^p+i^p) //
&/equiv (a+i)(a-i) //
&/equiv a^2-i^2 //
&/equiv n /pmod p
/end{aligned}
/]

/(p+1/) 为偶数，开方就很容易了
具体实现弄上“复数”即可
且 /((a+i)^{/frac{p+1}2}/) 的“虚部” 为 /(0/)

/(/text{Code}/)

#include <cstdio>
#include <algorithm>
#include <iostream>
#define IN inline
using namespace std;
typedef long long LL;

int T, n, p;
LL i2;

struct complex {
	LL x, y;
	IN complex(LL _x, LL _y) {x = _x, y = _y;}
	IN bool operator == (complex a) {return (a.x == x && a.y == y);}
	IN complex operator * (complex a) {
		return complex((a.x * x % p + a.y * y % p * i2 % p) % p, (a.x * y % p + a.y * x % p) % p);
	}
};

IN complex power(complex x, int y) {
	complex s = complex(1, 0);
	for(; y; y >>= 1, x = x * x) if (y & 1) s = s * x;
	return s;
}
IN int check(LL a) {return power(complex(a, 0), p - 1 >> 1) == complex(1, 0);}

IN void solve() {
	if (!n) {printf("0/n"); return;}
	if (power(complex(n, 0), p - 1 >> 1) == complex(p - 1, 0)) {printf("Hola!/n"); return;}
	LL a = rand() % p;
	while (!a || check((a * a % p - n + p) % p)) a = rand() % p;
	i2 = (a * a % p - n + p) % p;
	int x0 = power(complex(a, 1), p + 1 >> 1).x, x1 = p - x0;
	if (x0 > x1) swap(x0, x1);
	printf("%d %d/n", x0, x1);
}

int main() {
	scanf("%d", &T);
	for(; T; --T) scanf("%d%d", &n, &p), solve();
}