#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<array>
#include<unordered_map>
#include<vector>
#include<bitset>
#include<queue>
#include<set>
#include<map>
#include<ctime>
#include<random>
#include<numeric>
using namespace std;
#define int long long
#define ll long long
#define ull unsigned long long
#define lc (x<<1)
#define rc (x<<1|1)
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
const int Mx=1005;
int read(){
	char ch=getchar();
	int Alice=0,Aya=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-') Aya=-Aya;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		Alice=(Alice<<3)+(Alice<<1)+(ch^48),ch=getchar();
	return (Aya==1?Alice:-Alice);
}
int n,m,p;
int binom[Mx][Mx];
int f[Mx][Mx],mxd;
int Calc(int M,int i,int j,int d){
	//cout<<i<<" "<<j<<endl;
	if(i==0) return 1;
	if(f[i][d]) return f[i][d];
	if(i<=M) return f[i][d]=j*Calc(M,i-1,j,d)%p;
	else return f[i][d]=j*(Calc(M,i-1,j,d)-binom[i-1][M]*Calc(M,i-M-1,j-1,d+1)%p)%p;
}
void Solve(){
	n=read(),m=read();
	int ans=0;
	int lst=0;
	for(int M=1;M<=n;M++){
		for(int i=0;i<=n;i++) for(int j=0;j<=n/M;j++) f[i][j]=0;
		int v=Calc(M,n,m,0);
		(ans+=(v-lst)*M%p)%=p;
		lst=v;
	}
	cout<<(ans+p)%p<<endl;
}
signed main(){
	int T=read();
	p=read();
	for(int i=0;i<Mx;i++){
		binom[i][0]=1;
		for(int j=1;j<=i;j++) binom[i][j]=(binom[i-1][j-1]+binom[i-1][j])%p;
	}
	while(T--) Solve();
	return 0;
}
/*
Hello!!
Sample:
3 123456789
3 2
5 5
7 7
-------------------
*/