#include<bits/stdc++.h>
using namespace std;
const int maxn=2024;
long long a[maxn][maxn];
int main(){
//	freopen("T1.in","r",stdin);
//	freopen("T1.out","w",stdout);
	int t,k;
	cin>>t>>k;
	while(t--){
		int n,m,ans=0;
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			a[i][1]=i;
			int x=i;
			if(i>m)x=m;
			for(int j=2;j<=x;j++){
				a[i][j]=(a[i-1][j]+a[i-1][j-1])%k;
				if(j==i)a[i][j]=1;
			}
		}
		for(int i=1;i<=n;i++){
			int x=i;
			if(i>m)x=m;
			for(int j=1;j<=x;j++)
				if(a[i][j]%k==0)ans++;
		}
		cout<<ans<<endl;
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}