#include<cmath>
#include<cstdio>
#include<stdio.h>
#include<iostream>
using namespace std;
long long t,k,n,m,s;
long long a[2005][2005];
int main()
{
	cin>>t>>k;
	for(int o=1;o<=t;o++)
	{
		cin>>n>>m;
		a[0][0]=1;
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<=i;j++)
			{
				a[i][j]=a[i-1][j]+a[i-1][j-1];
			}
		}
		for(int i=0;i<=n;i++)
		{
			for(int j=0;j<=min(i,m);j++)
			{
				if(a[i][j]%k==0)
				{
					s++;
				}
			}
		}
		cout<<s<<endl;
		s=0;
	}
	return 0;
}