#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1003;
ll H,n,m,f[N][N],C[N][N];
void Solve()
{
	cin>>n>>m;ll res=1,ans=0;
	for(int i=1;i<=n;i++)res=res*m%H,ans=res;
	for(int k=1;k<=n;k++)
	{
		ll lim=n/k;memset(f,0,sizeof(f));
		for(int i=0;i<=lim;i++)f[0][i]=1;
		for(int i=0;i<=n;i++)f[i][lim+1]=0;
		for(int i=1;i<=n;i++)for(int j=0;j<=min(lim,m);j++)
		{
			f[i][j]=f[i-1][j]*(m-j)%H;
			if(i>k)f[i][j]=(f[i][j]-f[i-k-1][j+1]*C[i-1][k]%H*(m-j)%H+H)%H;
		}
		ans=(ans+res-f[n][0]+H)%H;
	}
	cout<<ans<<endl;
}
int main()
{
	int T;cin>>T>>H;
	for(int i=0;i<N;i++)for(int j=C[i][0]=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%H;
	while(T--)Solve();
}