#include<bits/stdc++.h>
using namespace std;
int n,m;
int t,k;
long long a[2055][2055];
int main()
{
	cin>>t>>k;
	for(int i=0;i<=2050;i++)
	{
		a[i][0]=1;
	}
	for(int i=1;i<=2050;i++)
	{
		for(int j=1;j<=i+1;j++)
		 {
		 	a[i][j]=a[i-1][j]+a[i-1][j-1];
		 }
	}
	while(t--)
	{
		int cnt=0;
		cin>>n>>m;
		for(int i=0;i<=n;i++)
		{
			int tmp=min(i,m);
			for(int j=0;j<=tmp+2;j++)
			{
				if(a[i][j]%k==0&&a[i][j]!=0) cnt++;
			}
		}
		printf("%d\n",cnt);
	}
	return 0;
 }