#include<iostream>
#include<cstdio>

using namespace std;
typedef long long ll;

ll t,k;
const ll MAXN = 2000;
ll C[MAXN+1][MAXN+1];
void Initial()
{
    ll i,j;
    for(i=0; i<=MAXN; ++i)
    {
        C[0][i] = 0;
        C[i][0] = 1;
    }
    for(i=1; i<=MAXN; ++i)
    {
        for(j=1; j<=MAXN; ++j)
        C[i][j] = (C[i-1][j] + C[i-1][j-1]) % k;
    }
}
int main()
{
	freopen("problem.in", "r", stdin);freopen("problem.out", "w", stdout);
	cin>>t>>k;Initial();
	while(t--)
	{
		ll n,m,ans=0;
		cin>>n>>m;
		for(ll i=0; i<=n; i++)
			for(ll j=0; j<=min(i, m); j++)
				if(C[i][j]%k==0)ans++;
		cout<<ans;
	}
	return 0;
}