#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e7+10;
const int M=666666;
int T,R,f[N]={0,1},prime[M],tot,ans[N]={0,1};
bool vis[N]={0,1};
ll pows(int a,int b){
	if(b==0) return 1;
	if(b&1){
		return (a*pows(a,b-1))%R;
	}
	ll res=pows(a,b/2);
	return (res*res)%R;
}
int main(){
	cin>>T>>R;
	for(int i=2;i<N;i++){
		ll now=(f[i-1]*i)%R;
		f[i]=now;
	}
	for(int i=2;i<N;i++){
		if(!vis[i]) prime[++tot]=i;
		for(int j=1;j<=tot&&prime[j]*i<N;j++){
			vis[prime[j]*i]=1;
			if(prime[j]%i==0) break;
		}
	}
	for(int i=2;i<N;i++){
		ll now=ans[i-1];
		if(!vis[i]) now=((now*(i-1)%R)*pows(i,R-2))%R;
		ans[i]=now;
	}
	while(T--){
		int n,m;cin>>n>>m;
		cout<<f[n]*ans[m]%R<<endl;
	}
	return 0;
}