#include<cstdio>
#include<iostream>

using namespace std;

const int maxn = 2000;
int T, k, n, m;
int c[2005][2005], f[2005][2005];

void init(int t) {
	for (int i = 0; i <= t; i++) c[i][i] = c[i][0] = 1;
	for (int i = 1; i <= t; i++) 
		for (int j = 1; j <= i; j++) {
			c[i][j] = (c[i-1][j-1] + c[i-1][j]) % k;
			if (j != i) f[i][j] = f[i][j-1] + f[i-1][j] - f[i-1][j-1] + (!c[i][j]);
			else f[i][j] = f[i][j-1] + (!c[i][j]);
		}
}

inline int read() {
	int x = 0; char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') x = (x<<1) + (x<<3) + (ch^48), ch = getchar();
	return x;
}

int main() {
	freopen("problem.in", "r", stdin);
	freopen("problem.out", "w", stdout);
	T = read(), k = read();
	init(2001);
	while (T--) {
		n = read(), m = read();
		if (m > n) m = n;
		printf("%d\n", f[n][m]);
	}
}