#include <bits/stdc++.h>
using namespace std;
int n,k;
long long pow(int a){
	if(a==0)return 1;
	return a*pow(a-1);
}
long long c(int a,int b){
	return (pow(a)/(pow(b)*pow(a-b)));
}

int main(){
	cin>>n>>k;
	int a1,a2;
	while (n--){
		cin>>a1>>a2;
		int sum=0;
		for(int i=0;i<=a1;i++){
			for(int j=0;j<=min(i,a2);j++){
				if(c(i,j)%k==0)sum++;
			}
		}
		cout<<sum<<endl;
	}
	return 0;
}