# p 为奇素数

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int q=0;char ch=' ';
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
return q;
}
int T,a,p,bin[22];
int ksm(int x,int y,int p) {
int re=1;
for(;y;y>>=1,x=1LL*x*x%p) if(y&1) re=1LL*re*x%p;
return re;
}
int jud(int x,int p) {return ksm(x,(p-1)/2,p)==1;}
void work() {
int s=p-1,b,t=0;
while(!(s&1)) ++t,s>>=1;
int inva=ksm(a,p-2,p),e=ksm(a,s,p),x=ksm(a,(s+1)/2,p);
while("xzy is too strong") {
b=rand()%p+1,b=((b*b-a)%p+p)%p;
if(b&&!jud(b,p)) break;
}
for(RI k=1;k<t;++k)
if(ksm(e,bin[t-k-1],p)!=1)
x=1LL*x*ksm(b,bin[k-1]*s,p)%p,e=1LL*inva*x%p*x%p;
int x1=x,x2=p-x;
if(x1>x2) swap(x1,x2);
printf("%d %d\n",x1,x2);
}
int main()
{
srand(19260817);
bin[0]=1;for(RI i=1;i<=20;++i) bin[i]=bin[i-1]<<1;
while(T--) {
if(p==2) {puts("1");continue;}
if(!jud(a,p)) {puts("No root");continue;}
work();
}
return 0;
}


# p 为奇素数的幂

$$(g^{2k})^{\frac{\phi(p^q)}{2}} = (g^k)^{\phi(p^q)} \equiv 1 \pmod{p^q}$$

$$(g^{2k+1})^{\frac{\phi(p^q)}{2}} \equiv g^{\frac{\phi(p^q)}{2}} \pmod(p^q)$$

# p 为 2 的幂

$$(y _ {k-1}+t _ {k-1}2^{k-2})^2 \equiv a _ k \pmod{2^k}$$

$$y _ {k-1}^2 + t _ {k-1}2^{k-1} \equiv a _ k \pmod{2^k}$$
$$t _ {k-1}2^{k-1} \equiv a _ k -y _ {k-1}^2 \pmod{2^k}$$
$$t _ {k-1} \equiv \frac{a _ {k} – y _ {k-1}^2}{2^{k-1}} \pmod{2}$$

$$x _ k = \pm (y _ {k-1}+\frac{a _ k- y _ {k-1}^2}{2} + 2^{k-1}t _ k)$$