#include<bits/stdc++.h>
//#pragma GCC optimize(3)
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define ll long long
#define ull unsigned ll
#define db double
#define ldb long db
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pbI push_back
#define inf 1e9
#define mdI int mid=(l+r)>>1
#define lowbit(x) (x&-x)
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define MAXN 1010
#define gint __int128
#define MOD 998244353
int qread(){
	char o=getchar();int f=1,x=0;
	for(;!isdigit(o);o=getchar())if(o=='-')f*=-1;
	for(;isdigit(o);o=getchar())x=x*10+o-'0';
	return f*x;
}
void chmx(int &x,int y){if(y>x)x=y;}
void chmi(int &x,int y){if(y<x)x=y;}
bool FLA;
namespace MathPart{
	#define rep(a,b,c) for(int a=b;a<=c;a++)
	#define vep(a,b,c) for(int a=b;a>=c;a--)
	void exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1,y=0;return;}exgcd(b,a%b,y,x);y-=(a/b)*x;}
	ll inv(ll a,ll p=MOD){ll x,y;exgcd(a,p,x,y);return (x+p)%p;}
	gint qp(ll a,ll b,ll p=MOD){gint rs=1,bs=a;while(b){if(b&1){rs=rs*bs%p;}bs=bs*bs%p;b>>=1;}return rs;}
	ll fac[MAXN],ifac[MAXN];
	void initF(ll n,ll p=MOD){
		fac[0]=1;rep(i,1,n){fac[i]=fac[i-1]*i%p;}
		ifac[n]=inv(fac[n],p);vep(i,n-1,0){ifac[i]=ifac[i+1]*(i+1)%p;}
	}
	ll C(ll n,ll m){if(n<m){return 0;}return fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;}
	ll CC(ll n,ll m,ll p=MOD){ll rs=1;rep(i,0,m-1){rs=rs*(n-i)%p*inv(i+1,MOD)%p;}return rs;}
	ll S2OL(ll n,ll m){
		ll rs=0,d=1,f=1;
		for(ll k=0;k<=m;k++){
			rs=(rs+f*C(m,k)*qp(m-k,n,MOD)%MOD+MOD)%MOD;
			d=d*max(k,1ll)%MOD;f*=-1;
		}return rs*inv(d,MOD)%MOD;
	}
	ll phi(ll a){ll rs=a,m=sqrt(a);
		rep(i,2,m){if(a%i==0){rs=rs/i*(i-1);while(a%i==0){a/=i;}}}
		if(a>1){rs=rs/a*(a-1);}return rs;
	}
	bool MR(ll pr){if(pr<2)return 0;if(pr==3)return 1;if(pr==2)return 1;
		ll a=pr-1,b=0;while(!(a&1))a>>=1,b++;
		for(int i=1;i<=8;++i){
		    ll x=rand()%(pr-2)+2,v=qp(x,a,pr),j;if(v==1||v==pr-1)continue;
		    for(j=0;j<b-1;j++){v=(gint)v*v%pr;if(v==pr-1)break;}
			if(v!=pr-1)return 0;
		}return 1;
	}
}
//using namespace MathPart;
int T,mod;
int C[MAXN][MAXN];
int dp[MAXN][MAXN];
int te[MAXN];
bool FLB;
signed main(){
	cerr<<((&FLB)-(&FLA))/1024.0/1024<<endl;
	cin>>T>>mod;
	rep(i,0,1e3){C[i][0]=1;}rep(i,1,1e3)rep(j,1,1e3){C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;}
	while(T--){
        int n=qread(),m=qread();
        int ans=0;
        rep(k,1,n){
            rep(j,0,m)dp[0][j]=1;
            rep(i,1,n){
                rep(j,0,min((n-i)/k,m-1)){
                    int ne=0;
                    dp[i][j]=dp[i-1][j]*(m-j)%mod;
                    if(i>=k+1)dp[i][j]=(dp[i][j]-C[i-1][k]*dp[i-k-1][j+1]%mod*(m-j)%mod+mod)%mod;
                }
            }
            te[k]=dp[n][0];
            rep(i,1,n)rep(j,0,min((n-i)/k,m-1))dp[i][j]=0;
            rep(j,0,min(n/k,m-1))dp[0][j]=0;
        }
        rep(k,1,n)ans=(ans+(te[k]-te[k-1])*k)%MOD;
        printf("%lld\n",ans);
	}
}
/*
3 123456789
3 2
5 5
7 7
*使用球盒模型描述问题(重在换)
考虑<=k
n个相互区分之小球放入m个相互区分之盒子，每一个应<=k
需要递推，一个一个盒子考虑，难以变优。
从球考虑,f[n][m]=f[n-1][m]*m-C(n-1,k)f[n-k-1][m-1]  (这个是容斥角度)    (如果没有远虑的话，挺难考虑把m作为下标的)
实际上有用的m极少,边界在n=0时，因为m至多减少n/k,变换递推式
f[n][dm]=f[n-1][dm]*(m-dm)-C(n-1,k)-C(n-1,k)f[n-k-1][dm+1]
边界在n=0时,值为1,实际上直接每组T求即可

考虑(m-dm)会不会为负，显然有变为0的过程,定然为0
*/