#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1005;
namespace FastMod {
typedef unsigned long long ull;
typedef __uint128_t uLL;
ull b,q,r; uLL m;
inline void init(const ull &B) { b=B,m=(uLL(1)<<64)/B; }
inline ull mod(const ull &a) {
	r=a-((m*a)>>64)*b;
	return r>=b?r-b:r;
}
};
#define o(x) FastMod::mod(x)
int n,m,MOD;
ll C[MAXN][MAXN],f[MAXN][MAXN];
ll calc(int k) {
	int up=min(n/k,m);
	for(int i=0;i<=up;++i) f[0][i]=1;
	for(int i=1;i<=n;++i) for(int j=0;j<=up;++j) {  //f[i,m-j]
		f[i][j]=o(o(f[i-1][j]+(i<k?0:(MOD-f[i-k][j+1])*C[i-1][k-1]))*(m-j));
	}
	ll ans=f[n][0];
	for(int i=0;i<=n;++i) memset(f[i],0,sizeof(ll)*(up+1));
	return ans;
}
void solve() {
	cin>>n>>m;
	ll tot=1,ans=0;
	for(int i=1;i<=n;++i) tot=o(tot*m);
	for(int k=1;k<=n;++k) ans=o(ans+tot+MOD-calc(k));
	cout<<ans<<"\n";
}
signed main() {
	ios::sync_with_stdio(false);
	int T; cin>>T>>MOD,FastMod::init(MOD);
	for(int i=0;i<MAXN;++i) for(int j=C[i][0]=1;j<=i;++j) C[i][j]=o(C[i-1][j]+C[i-1][j-1]);
	while(T--) solve();
	return 0;
}