#include <bits/stdc++.h>

const int N = 2e3;
int C[N + 5][N + 5],S[N + 5][N + 5],t,k;

int main() {
	freopen("problem.in","r",stdin);
	freopen("problem.out","w",stdout);
	scanf("%d %d",&t,&k);
	memset(C , -1 , sizeof(C));
	C[0][0] = 1 % k;
	for(int i = 1;i <= N;++ i) {
		C[i][0] = 1 % k;
		for(int j = 1;j <= i;++ j) {
			C[i][j] = 0;
			if(~ C[i - 1][j])
				(C[i][j] += C[i - 1][j]) %= k;
			if(~ C[i - 1][j - 1])
				(C[i][j] += C[i - 1][j - 1]) %= k;
		}
	}
	S[0][0] = C[0][0] == 0;
	for(int i = 1;i <= N;++ i)
		S[i][0] = (S[i - 1][0] + (C[i][0] == 0)),S[0][i] = (S[0][i - 1] + (C[i][0] == 0));
	for(int i = 1;i <= N;++ i) {
		for(int j = 1;j <= N;++ j) {
			S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + (C[i][j] == 0);
		}
	}
	while(t --) {
		int n,m;
		scanf("%d %d",&n,&m);
		printf("%d\n",S[n][m]);
	}
	return 0;
}