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

int md;

inline int add(int x, int y) {
	if (x + y >= md) return x + y - md;
	return x + y;
}

inline int sub(int x, int y) {
	if (x < y) return x - y + md;
	return x - y;
}

inline int mul(int x, int y) {
	return 1ull * x * y % md;
}

inline int fpow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = mul(ans, x);
		y >>= 1; x = mul(x, x);
	}
	return ans;
}

const int N = 1005;

int dp[N][N], C[N][N];
int T, n, m;

int main() {
	cin >> T >> md;
	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] = add(C[i - 1][j - 1], C[i - 1][j]);
	}
	while (T--) {
		cin >> n >> m;
		int all = fpow(m, n), ans = all;
		for (int b = 2; b <= n; b++) {
			// < b
			memset(dp[0], 0, sizeof(dp[0]));
			for (int i = 0; i <= n / b; i++) dp[0][i] = 1;
			for (int i = 1; i <= n; i++) {
				for (int j = 0; j <= min(m, n / b); j++) {
					dp[i][j] = dp[i - 1][j];
					dp[i][j] = sub(dp[i][j], mul(dp[i - b][j + 1], C[i - 1][b - 1]));
					dp[i][j] = mul(dp[i][j], m - j);
				}
				dp[i][n / b + 1] = 0;
			}
			ans = add(ans, sub(all, dp[n][0]));
		}
		printf("%d\n", ans);
	}
	return 0;
}