#include<cstdio>
#include<cstring>
#define syy myson
using namespace std;
typedef long long LL;
int t,k,n,m,c[2001][2001],sum[2001][2001],i,j;
int Main()
{
	freopen("problem.in","r",stdin);freopen("problem.out","w",stdout);
	scanf("%d%d",&t,&k);
	memset(c,0,sizeof(c));
	for(i=1;i<=2000;i++)
	{
		c[i][0]=1;
		c[i][i]=1;
	}
	for(i=2;i<=2000;i++)for(j=1;j<=i;j++)
	{
		c[i][j]=c[i-1][j-1]+c[i-1][j];
		c[i][j]%=k;
	}
	for(i=1;i<=2000;i++)for(j=1;j<=i;j++)
	{
		if(c[i][j])c[i][j]=0;
		else c[i][j]=1;
	}
	for(i=1;i<=2000;i++)for(j=1;j<=2000;j++)
		sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+c[i][j];
	while(t--)
	{
		scanf("%d%d",&n,&m);
		m=n<m?n:m;
		printf("%d\n",sum[n][m]);
	}
}
int main(){;}
int syy=Main();