#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e7+1;
typedef long long ll;
int T,n,m;
int P,fac[N],inv[N],cal[N];
bool nonprime[N];
int prime[700010],cnt;

void Prime() {
    for (int i=2;i<N;i++) {
        if (!nonprime[i]) prime[++cnt]=i;
        for (int j=1;j<=cnt;j++) {
            if (1ll*i*prime[j]>=N) break;
            nonprime[i*prime[j]]=1;
            if (i%prime[j]==0)     break;
        }
    }
    inv[1]=1;fac[1]=1;cal[1]=1;
    for (int i=2;i<N;i++) {
        inv[i]=1ll*(P-P/i)*inv[P%i]%P,fac[i]=1ll*fac[i-1]*i%P;
        cal[i]=1ll*cal[i-1]*(nonprime[i]?1:1ll*(i-1)*inv[i]%P)%P;
    }
}

int main() {
    scanf("%d%d",&T,&P);
    Prime();
    while (T--) {
        scanf("%d%d",&n,&m);
        printf("%d\n",1ll*fac[n]*cal[m]%P);
    }
}