#include <bits/stdc++.h>

using namespace std;


const int N=(int)1e5+19;

int n,T,p;

int kpow(int a,int b,int p){
    int t=1;

    while(b){
        if(b&1)t=t*a%p;
        a=a*a%p;
        b>>=1;
    }

    return t;
}

bool ist(int n,int p){
    return kpow(n,(p-1)>>1,p)==1;
}

int zpow(complex <int> z,int b){
    complex <int> t(1,0);

    while(b){
        if(b&1)t=t*z;
        z=z*z;
        b>>=1;
    }

    return t.real();
}

int main(){
    srand(time(NULL));

    cin>>T;

    while(T--){
        cin>>n>>p;

        if(n==0){
            cout<<n<<"\n";
            continue;
        }

        if(!ist(n,p))cout<<"Hola!\n";
        else{
            while(1){
                int a=rand();

                if(!ist(a*a-n,p)){
                    complex <int> t(a,1);
                    
                    int ans1=zpow(t,(p+1)>>1);
                    int ans2=-ans1;

                    if(ans1>0)cout<<ans2<<' '<<ans1<<"\n";
                    else cout<<ans1<<' '<<ans2<<"\n";

                    break;
                }
            }
        }
    }
    return 0;
}