#include<bits/stdc++.h>
using namespace std;

int jiecheng(int n){
	if(n==0){
		return 1;
	}
	int a=1;
	for(int i=1;i<=n;i++){
		a=a*i;
	}
	return a;
}
int main(){
	unsigned long long t,k,ans=0;
	cin>>t>>k;
	unsigned long long a[t],d=0;
	for(int i=0;i<t;i++){
		int n,m,c;
		cin>>n>>m;
		for(int i=0;i<=n;i++){
			for(int j=0;j<=min(i,m);j++){
			c=jiecheng(i)/(jiecheng(j)*jiecheng(i-j));
				if(c%k==0){
					ans++;
				}
			}
		}
		a[d]=ans;
		ans=0;
		d++;
	}
	for(int i=0;i<t;i++){
		cout<<a[i]<<endl;
	}
	return 0;
}