#include<bits/stdc++.h>
#ifdef ONLINE_JUDGE
	#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
	char buf[1<<21],*p1=buf,*p2=buf;
#endif
using namespace std;int read(){int num=0,f=1;char c;while(!isdigit(c=getchar()))if(c=='-')f=-1;while(isdigit(c))num=num*10+(c&15),c=getchar();return num*f;}void write(int x,char ch=' '){int F[20],cnt=0;if(!x)putchar('0');if(x<0)putchar('-'),x=-x;while(x)F[cnt++]=x%10+'0',x/=10;while(cnt)putchar(F[--cnt]);putchar(ch);}
namespace Main
{
    const int N=10000010;int n,mod,ifac[N],fac[N],inv[N],x,y,z,xx,yy,zz,ans;int ksm(int x,int y=mod-2){int res=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)res=1ll*res*x%mod;return res;}int C(int x,int y){return 1ll*fac[x]*ifac[y]%mod*ifac[x-y]%mod;}
    void main()
    {
        n=read(),mod=read(),ans=0,fac[0]=inv[0]=inv[1]=ifac[0]=1;for(int i=2;i<=n;++i)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;for(int i=1;i<=n+1;++i)fac[i]=1ll*fac[i-1]*i%mod,ifac[i]=1ll*ifac[i-1]*inv[i]%mod;
        // for(int i=0;i<=2*n;++i)printf("%d%c",inv[i]," \n"[i==2*n]);for(int i=0;i<=2*n;++i)printf("%d%c",fac[i]," \n"[i==2*n]);for(int i=0;i<=2*n;++i)printf("%lld%c",1ll*fac[i]*ifac[i]%mod," \n"[i==2*n]);
        for(int i=z=1;i<=n;++i)z=2*z%mod,ans=(ans+1ll*z*C(n,i-1)%mod*C(n,i))%mod/*,printf("#%d %lld\n",z,1ll*z*C(n,i)%mod*C(n,i-1)%mod)*/;write((fac[n+1]-1ll*ans*ksm(n)%mod+mod)%mod,'\n');
    }
};
int main()
{
    // freopen("sort.in","r",stdin),freopen("sort.out","w",stdout);
    const bool base=1,IO=1;int T;if(!base)T=1;else if(IO)T=read();else ios::sync_with_stdio(0),cin>>T;for(;T--;)Main::main();
    return 0;
}