RT

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,p,i,t;
struct node {
	int a,b;
} ans;
node Mul(node x,node y) {
	node res;
	res.a=res.b=0;
	res.a=(((x.a*y.a)%p)+((((x.b*y.b)%p)*i)%p))%p;
	res.b=(((x.a*y.b)%p)+((x.b*y.a)%p))%p;
	return res;
}
int rfpow(int x,int y) {
	cout<<x<<' '<<y<<endl;
	int res=1;
	while(y) {
		if(y&1)res=(res*x)%p;
		x=(x*x)%p;
		y>>=1;
	}
	cout<<res%p<<endl;
	return res%p;
}
int ifpow(node x,int y) {
	node res;
	res.a=1,res.b=0;
	while(y) {
		if(y&1)res=Mul(res,x);
		x=Mul(x,x);
		y>>=1;
	}
	return res.a%p;
}
signed main() {
	scanf("%lld",&T);
	while(T--) {
		scanf("%lld%lld",&n,&p);
		n%=p,t=0;
		if(!n) {
			printf("0\n");
			continue;
		}
		if(rfpow(n,(p-1)>>1)==p-1){
			printf("Hola!\n");
			continue;
		}
		while(1) {
			t=rand()%(p-1)+1;
			i=(((t*t)%p)-n+p)%p;
			if(rfpow(i,(p-1)>>1)==p-1)break;
		}
		ans.a=t,ans.b=1;
		int res1=ifpow(ans,(p-1)>>1);
		int res2=p-res1;
		printf("%lld %lld\n",min(res1,res2),max(res1,res2));
	}
}