#include <bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T &x)
{
    x=0;char c=getchar();bool f=0;
    for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c-'0');
    x=(f?-x:x);
}
const int N = 1020;
int dp[N][N];
int n,m,mod,C[N][N];
void solve()
{
    read(n);read(m);
    int r=0,ans=0;
    for(int k=1;k<=n;k++)
    {
        int lim=min(m,n/(k+1));
        for(int i=0;i<=n;i++)
        for(int j=lim;j>=0;j--)
        if(i<=k)dp[i][j]=(i==0?1:1ll*dp[i-1][j]*(m-j)%mod);
        else if(j<m)dp[i][j]=(1ll*dp[i-1][j]*(m-j)%mod-1ll*(m-j)*C[i-1][k]%mod*dp[i-(k+1)][j+1]%mod+mod)%mod;
        int w=dp[n][0];
        ans=(ans+1ll*k*(w-r+mod)%mod)%mod;r=w;
    }
    printf("%d\n",ans);
}
int main()
{
    int T;
    read(T);read(mod);
    for(int i=0;i<=1000;i++)
    {
        C[i][0]=1;
        for(int j=1;j<=i;j++)
        C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    while(T--)
    {
        solve();
    }
	return 0;
}