//
#include<bits/stdc++.h>
#define ll long long
#define int ll
#define fs first
#define se second
#define PII pair<int,int>
#define ull unsigned long long
#define db double
#define all(s) s.begin(),s.end()
#define PB push_back
using namespace std;
//[b + 1, a!]中的质数（与a!互质的数）
//phi(a!) - prime(1~b) + 1
vector<int> prime;
void Eula(int n){
    bitset<10000007>a;
    for(int i = 2; i <= n; i ++){
        if(!a[i])prime.push_back(i);
        for(auto j : prime){
            if(i * j > n)break;
            a[i * j] = 1;
            if(i % j == 0)break;
        }
    }
}
int qp(int a, int b, int mod){
    int t = 1;
    while(b){
        if(b & 1)t = t * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return t;
}
const int N = 1e7 + 7;
int f[N];
int inv[N];
int preprime[N];
int preinv[N];
void solve(){
    int T, mod;
    cin >> T >> mod;
    Eula(10000000);
    // cerr << prime.size();
    f[0] = 1;
    for(int i = 1; i <= 10000000; i ++)f[i] = i != mod ? f[i - 1] * i % mod : f[i - 1];
    inv[1] = 1;
    for(int i = 2; i <= 10000000; i ++)inv[i] = inv[mod % i]* (mod - mod / i) % mod;
    preprime[0] = 1;
    preinv[0] = 1;
    int f1 = 1, f2 = 1;
    for(int i = 1; i <= 664579; i ++){
        if((prime[i - 1] - 1) % mod == 0 && f1)preprime[i] = preprime[i - 1], f1 = 0;
        else preprime[i] = preprime[i - 1] * (prime[i - 1] - 1) % mod;
        if(inv[prime[i - 1]] % mod == 0 && f2) preinv[i] = preinv[i - 1] , f2 = 0;
        else preinv[i] =preinv[i - 1] * inv[prime[i - 1]] % mod;
    }
    while(T --){
        int a, b;
        cin >> a >> b;
        int res = f[b];
        // cerr << res << "\n";
        // for(int i : prime){
        //     if(i > b)break;
        //     res = res * (i - 1) % mod * inv[i] % mod;
        //     // cerr << res << " " << i << "\n";
        // }
        int p = upper_bound(all(prime), b) - prime.begin();
        res = res * preprime[p] % mod * preinv[p] % mod;
        // cerr << preprime[p] << " " << preinv[p];
        cout <<f[a] * qp(f[b], mod - 2, mod) % mod * res % mod << "\n";
    }
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
//	freopen("1.txt","r",stdin);
	int T=1;
//	cin>>T;
	while(T--){
		solve();
	}
}