#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
int T,k,n,m;
const int maxn=2000;
long long c[2005][2005],f[2005][2005];
void init(int t)
{
	for(int i=0;i<=t;i++)c[i][0]=c[i][i]=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;
	for(int i=1;i<=t;i++)
	for(int j=1;j<=t;j++)
	{
		f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
		if(!c[i][j]&&i>=j)++f[i][j];
	}
}
int main()
{
	freopen("problem.in","r",stdin);
	freopen("problem.out","w",stdout);
	scanf("%d%d",&T,&k);
	init(2001);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		printf("%d\n",f[n][m]);
	}
}