#include<iostream>
#include<bits/stdc++.h>
using namespace std;
long long t,n,m,k,f[2000+10][2000+10],s[2000+10][2000+10];
int main()
{
	freopen("problem.in","r",stdin);
	freopen("problem.out","w",stdout);
	scanf("%lld%lld",&t,&k);
	for(int i=0;i<=2000;i++)
		{
			f[i][i]=1;
			f[i][0]=1;
		}
	for(int i=1;i<=2000;i++)
		for(int j=1;j<i;j++)
		{
			f[i][j]=(f[i-1][j-1]+f[i-1][j])%k;
		}
	for(int i=1;i<=2000;i++)
		for(int j=1;j<=2000;j++)
		{
			 s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1];
            	if(f[i][j]==0&&j<=i)
                	s[i][j]++;
		}
	for(int i=1;i<=t;i++)
	{
		long long ans=0;
		scanf("%lld%lld",&n,&m);
		printf("%lld\n",s[n][m]);
	}
	
}