#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long Lint;

const int maxT=20000;

const int maxn=10000009;

int T,r;

int mn=0,mm=0;

int inn[maxT];

int inm[maxT];

Lint fac[maxn];

int vis[maxn]= {0};

int prime[maxn],cntprime=0;

int Lineshake() {

	vis[1]=1;

	for(int i=2; i<=mm; ++i) {

		if(!vis[i]) {

			prime[++cntprime]=i;

		}

		for(int j=1; (j<=cntprime)&&(i*prime[j]<=mm); ++j) {

			vis[i*prime[j]]=1;

			if(i%prime[j]==0)break;

		}

	}

}

Lint ksm(Lint a,Lint p) {

	Lint ret=1;

	for(; p; p>>=1,a=a*a%r) {

		if(p&1)ret=ret*a%r;

	}

	return ret;

}

Lint inv(Lint x) {

	return ksm(x,r-2);

}

Lint phi[maxn];

int main() {

	scanf("%d%d",&T,&r);

	for(int i=1; i<=T; ++i) {

		scanf("%d%d",&inn[i],&inm[i]);

		mn=max(mn,inn[i]);

		mm=max(mm,inm[i]);

	}

	fac[1]=1;

	for(int i=2; i<=mn; ++i)fac[i]=fac[i-1]*i%r;

	Lineshake();

	phi[1]=1;

	for(int i=2; i<=mm; ++i) {

		if(!vis[i]) {

			phi[i]=phi[i-1]*(i-1)%r*inv(i)%r;

		} else {

			phi[i]=phi[i-1];

		}

	}

	for(int i=1; i<=T; ++i) {

		printf("%lld\n",fac[inn[i]]*phi[inm[i]]%r);

	}

	return 0;

}