#include<bits/stdc++.h>
using namespace std;
int m,n,k,t,a[3000][3000],ans;

int f(int x,int y) {
	if(x<0||y<0)return 0;
	else if(x==y) {
		a[x][y]=1;
		return 1;
	} else if(a[x][y]==0) {
		a[x][y]=f(x-1,y-1)+f(x-1,y);
		return a[x][y];
	} else
		return a[x][y];
}//构造杨辉三角

int main() {
	cin>>t>>k;
	for (int i=1; i<=t; i++) {
		cin>>n>>m;
		for(int j=0; j<=n; j++)
			f(n,j);//执行构造
		for(int j=0; j<=n; j++)
			for(int u=0; u<=min(j,m); u++)
				if(a[j][u]%k==0)
					ans++;//遍历杨辉三角
		cout<<ans<<endl;
	}

	return 0;
}

思路，先构造一个杨辉三角，再进行遍历，知道会超时，但是想要知道为什么会WA https://www.luogu.com.cn/record/178975824 求大佬指点，谢谢