#include <bits/stdc++.h>

using namespace std;

int mod;

int add(int a, int b) {
	return a + b >= mod ? a + b - mod : a + b;
}

int sub(int a, int b) {
	return a >= b ? a - b : a + mod - b;
}

int mul(int a, int b) {
	return 1ll * a * b % mod;
}

int power(int a, int x) {
	int res = 1;
	while (x) {
		if (x & 1) {
			res = mul(res, a);
		}
		a = mul(a, a);
		x >>= 1;
	}
	return res;
}

constexpr int N = 8080;
int dp[N][N], cnk[N][N];

void solve() {
	int n, m;
	cin >> n >> m;
	int ans = power(m, n);
	for (int k = 1; k < n; k++) {
		int shift = max(m - n / k - 3, 1);
		for (int j = shift; j <= m; j++) {
			dp[0][j - shift] = 1;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = shift; j <= m; j++) {
				dp[i][j - shift] = mul(j, dp[i - 1][j - shift]);
				if (i - k - 1 >= 0 && j - 1 >= shift) {
					dp[i][j - shift] = sub(dp[i][j - shift], mul(j, mul(cnk[i - 1][k], dp[i - k - 1][j - 1 - shift])));
				}
			}
		}
		ans = add(ans, sub(power(m, n), dp[n][m - shift]));
	}
	cout << ans << '\n';
}

int32_t main() {
	std::cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	cin >> t >> mod;
	cnk[0][0] = 1;
	for (int i = 1; i < N; i++) {
		cnk[i][0] = 1;
		for (int j = 1; j < N; j++) {
			cnk[i][j] = add(cnk[i - 1][j], cnk[i - 1][j - 1]);
		}
	}
	while (t--) {
		solve();
	}
}