#模平方根的解法——托内利－尚克斯算法（Tonelli–Shanks algorithm）

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

long long MOD;

long long mod_exp(long long a,long long b) //二分快速幂
{
    long long res=1;
    while(b>0)
    {
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}

long long solve(long long n,long long p)
{
    int Q=p-1,S=0;
    while(Q%2==0)
    {
        Q>>=1;
        S++;
    }
    if(S==1)
    {
        return mod_exp(n,(p+1)/4);
    }
    int z;
    while(1)
    {
        z=1+rand()%(p-1);
        if(mod_exp(z,(p-1)/2)!=1) break;
    }
    long long c=mod_exp(z,Q);
    long long R=mod_exp(n,(Q+1)/2);
    long long t=mod_exp(n,Q);
    long long M=S,b,i;
    while(1)
    {
        if(t%p==1) break;
        for(i=1;i<M;i++)
        {
            if(mod_exp(t,1<<i)==1) break;
        }
        b=mod_exp(c,1<<(M-i-1));
        R=(R*b)%p;
        t=(t*b*b)%p;
        c=(b*b)%p;
        M=i;
    }
    return (R%p+p)%p;
}

int main()
{
    int T,a,n,i;
    cin>>T;
    while(T--)
    {
        cin>>a>>n;
        if(n==2)
        {
            if(a%n==1) cout<<1<<endl;
            else cout<<"No root"<<endl;
            continue;
        }
        MOD=n;
        if(mod_exp(a,(n-1)/2)!=1)
        {
            cout<<"No root"<<endl;
            continue;
        }
        i=solve(a,n);
        if(i==n-i) cout<<i<<endl;
        else cout<<min(i,n-i)<<" "<<max(i,n-i)<<endl;
    }
    return 0;
}