#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<iostream>
#include<string>
#include<cmath>
#define N 10000000
#define yy 1000
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ROF(i,a,b) for(i=(a);i>=(b);i--)
typedef long long LL;
using namespace std;
bool b[N+yy];int p[N+yy],len=0,Te,R;
int fac[N+yy],T[N+yy],F[N+yy];
LL powmod(LL x,LL p,LL MOD)
{
  LL e=x,ans=1;
  for(;p;p>>=1)
  {
    if (p&1) ans*=e,ans%=MOD;
    e*=e,e%=MOD;
  }
  return ans%MOD;
}
void facinit(int x,LL MOD)
{
  fac[0]=1;int i;
  FOR(i,1,x) fac[i]=(LL)fac[i-1]*(LL)i%MOD;
}
void initprime(LL MAX)
{
  len=0;int i,j;
  memset(b,0,sizeof(b));
  FOR(i,2,MAX)
  {
    if (!b[i]) p[++len]=i;
    FOR(j,1,len)
    {
      if (i*p[j]>MAX) break;
      b[i*p[j]]=1;
      if (i%p[j]==0) break;
    }
  }
}
void Main()
{
  int n,m;
  scanf("%d%d",&n,&m);
  int *p1=upper_bound(p+1,p+1+len,m);
  int P=p1-p-1;
  LL ny_tp=powmod(T[P],R-2,R);
  LL ans=(LL)fac[n]*(LL)F[P]%R*(LL)ny_tp%R;
  printf("%lld\n",(fac[n]-ans+R)%R);
}
int main()
{
  scanf("%d%d",&Te,&R);
  facinit(N,R);initprime(N);
  F[1]=1;T[1]=2;int i;
  FOR(i,2,len)
  {
    T[i]=(LL)T[i-1]*(LL)p[i]%R;
    F[i]=((LL)p[i]*(LL)F[i-1]%R+T[i-1]-F[i-1]+R)%R;
  }
  FOR(i,1,Te) Main();
}