#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define pii pair<int, int>
#define pll pair<LL, LL>
#define fi first
#define se second
#define mkp make_pair
#define sz(x) (int)x.size()
using namespace std;
bool Mst;

LL read() {
	LL s = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9')
		f = (ch == '-' ? -1 : 1), ch = getchar();
	while (ch >= '0' && ch <= '9')
		s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
	return s * f;
}

int n, m, mod;

int qpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1)
			res = (LL)res * a % mod;
		a = (LL)a * a % mod, b >>= 1;
	}
	return res;
}

auto fplus = [](int x, int y) {return x + y < mod ? x + y : x + y - mod;};
auto fminus = [](int x, int y) {return x >= y ? x - y : x + mod - y;};
auto Fplus = [](int &x, int y) {x = fplus(x, y);};
auto Fminus = [](int &x, int y) {x = fminus(x, y);};

const int N = 1000, MAXN = N + 5;
int f[1005][1005], res[1005], C[1005][1005];

bool Med;
signed main() {
	int t = read(); mod = read();
	C[0][0] = 1;
	for (int i = 1; i <= N; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j++) C[i][j] = fplus(C[i - 1][j], C[i - 1][j - 1]);
	}
	while (t--) {
		n = read(), m = read();
		for (int k = 1; k <= n; k++) {
			int lim = n / (k + 1);
			for (int i = 0; i <= n; i++)
				for (int j = 0; j <= lim; j++)
					f[i][j] = 0;
			f[0][0] = 1;
			for (int i = 0; i < n; i++)
				for (int j = 0; j <= lim; j++) {
					if (!f[i][j]) continue;
					int v = 1ll * (m - j) * f[i][j] % mod;
					Fplus(f[i + 1][j], v);
					if (i + k + 1 <= n) Fplus(f[i + k + 1][j + 1], 1ll * C[n - i - 1][k] * v % mod);
				}
			res[k] = 0;
			for (int i = 0; i <= lim; i++)
				(i & 1 ? Fminus : Fplus)(res[k], f[n][i]);
		}
		int ans = 0;
		for (int i = n; i; i--) {
			Fminus(res[i], res[i - 1]);
			Fplus(ans, 1ll * i * res[i] % mod);
		}
		printf("%d\n", ans);
	}
	return 0;
}