#pragma GCC optimize(2,3,"Ofast","inline","unroll-loops")
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=2e3+9;
ll T,n,m,Mod,C[N][N],ans[N],dp[N][N];
using L=__uint128_t;
struct FastMod{
    ull b,m;
    FastMod(ull b):b(b),m(ull((L(1)<<64)/b)){}
    ull operator()(ull a){
        ull q=(ull)((L(m)*a)>>64);
        ull r=a-q*b;
        return r>=b?r-b:r;
    }
}R(2);
ll pw(ll x,ll p){
    ll res=1;
    while(p){
        if(p&1)res=R(res*x);
        x=R(x*x),p>>=1;
    }
    return res;
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    T=read(),Mod=read();
    R=FastMod(Mod);
    rep(i,0,1000){
        C[i][0]=1;
        rep(j,1,i)C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod;
    }
    while(T--){
        n=read(),m=read();
        rep(k,1,n+1){
            dp[0][0]=1;
            rep(i,1,n){
                dp[i][i/k+1]=0;
                rep(j,0,i/k){
                    dp[i][j]=R(dp[i-1][j]*(m-j));
                    if(j&&i>=k)dp[i][j]=R(dp[i][j]+R(R(dp[i-k][j-1]*(m-j+1))*C[n-i+k-1][k-1]));
                    // cout<<"now"<<i<<" "<<j<<" "<<dp[i][j]<<endl;
                }
            }
            ans[k]=0;
            rep(i,0,n/k)ans[k]=(ans[k]+(!(i&1)?1ll:Mod-1)*dp[n][i])%Mod;
        }
        per(k,n+1,1)ans[k]=(ans[k]-ans[k-1]+Mod)%Mod;
        ll res=0;
        rep(k,1,n+1)res=(res+ans[k]*(k-1))%Mod;
        write(res),putchar('\n');
    }
    cerr<<"\n"<<clock()*1.0/CLOCKS_PER_SEC*1000<<"ms\n";
    return 0;
}