#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

long long a[2100][2100]={},b[2100][2100]={};
long long t,k;
void creat()
{
	long long n=2000;
	for(long long i=1;i<=n;i++)
	{
		a[i][1]=a[i][i]=1;
	}
	for(long long i=1;i<=n;i++)
	{
		for(long long j=2;j<i;j++)
		{
			a[i][j]=a[i-1][j]+a[i-1][j-1];
		}
	}
}
void num()
{
	for(long long i=1;i<=2000;i++)
	{
		for(long long j=1;j<=i;j++)
		{
			if(a[i][j]%k==0)
			{
				b[i][j]+=1;
			}
			b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
		}
	}
}
int main() 
{
	cin>>t>>k;
	creat();
	num();
	while(t>0)
	{
		t--;
		long long n,m;
		cin>>n>>m;
		cout<<b[n][m]<<endl;
	}
}