注意到 $[1,m]$ 都不与 $m!$ 互质，其他不与其互质的数都是 $[1,m]$ 的倍数，考虑到只数出 $[1,n!]$ 有多少个 $[1,m]$ 以内质数的倍数。这玩意和欧拉函数定义式的推导基本一直，读者自行蓝书。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+12;
int T,mod,cnt;
int mul[N],pri[N/10],ny[N/10];
struct node{
	int n,m,id;
}q[11010];int ans[11010];
bitset<N> vis;
int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=(res*a)%mod;
		b>>=1;a=(a*a)%mod;
	}return res;
}
bool cmp(node A,node B){
	return A.m<B.m;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T >> mod; 
	mul[0]=1; 
	for(int i=1;i<=N-10;++i){ //预处理阶乘 
		mul[i]=(mul[i-1]*i)%mod;
	}
	for(int i=2;i<=N-10;++i){//筛质数 
		if(vis[i]==0){
			pri[++cnt]=i;
		}
		for(int j=1;j<=cnt&&pri[j]*i<=N-10;++j){
			vis[pri[j]*i]=1;
			if(i%pri[j]==0) break;
		}
	}
	for(int i=1;i<=cnt;++i){//对质数处理逆元 
		ny[i]=qpow(pri[i],mod-2);
	}
	for(int i=1;i<=T;++i){//离线处理 
		cin >> q[i].n >> q[i].m;
		q[i].id=i;
	}sort(q+1,q+T+1,cmp);
	int j=1,tmp=1;
	for(int i=1;i<=cnt&&j<=T;++i){
		while(pri[i]>q[j].m){
//			cout << q[j].id <<' '<< q[j].n <<' '<<q[j].m<<" "<<'\n';
			ans[q[j].id]=(mul[q[j].n]*tmp)%mod;
			j++;
			if(j>T) break;
		}
		tmp=(tmp)*((1-ny[i]+mod)%mod)%mod;
	}
	for(int i=1;i<=T;i++){
		cout << ans[i] << '\n';
	}
	return 0;
}
/*

*/