#include<iostream>
using namespace std;
int n,m,a[2006][2006]={1},t,k;
int main(){
	cin>>t>>k;
	for(int i=0;i<2005;i++){
		for(int j=0;j<=i;j++){
			a[i+1][j]=(a[i+1][j]+a[i][j])%k;
			a[i+1][j+1]=(a[i+1][j+1]+a[i][j])%k;
		}
	}
	while(t--){
		cin>>n>>m;
		int sum=0;
		for(int i=0;i<=n;i++){
			for(int j=0;j<=min(i,m);j++){
				if(a[i][j]==0){
					sum++;
				}
			}
		}
		cout<<sum<<'\n';
	}
	return 0;
}