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

const int N = 1005;

int T, mod, n, m, ans, C[N][N], f[N][N], g[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> T >> mod;
	C[0][0] = 1;
	for (int i = 1; i <= 1000; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
		}
	}
	while (T--) {
		cin >> n >> m;
		for (int k = 1; k <= n; k++) {
			int lim = n / (k + 1);
			int bottom = max(m - lim, 1);
			for (int j = 0; j <= m - bottom; j++) {
				f[0][j] = 1;
				for (int i = 1; i <= n; i++) {
					f[i][j] = (1ll * f[i - 1][j] * (j + bottom) % mod - (i > k && j ? 1ll * f[i - k - 1][j - 1] * C[i - 1][k] % mod * (j + bottom) % mod : 0) + mod) % mod;
				}
			}
			g[k] = f[n][m - bottom];
		}
		ans = 0;
		for (int k = 1; k <= n; k++) {
			ans = (ans + 1ll * k * (g[k] - g[k - 1] + mod) % mod) % mod;
		}
		cout << ans << '\n';
	}

	return 0;
}