#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long t,k;
long long n,m;
long long c[2050][2050],a[2050][2050];
int main()
{
	freopen("problem.in","r",stdin);
	freopen("problem.out","w",stdout);
	scanf("%lld%lld",&t,&k);
	for(long long i=0;i<=2000;i++)
	{
		c[i][0]=1;c[i][i]=1;
		for(long long j=1;j<i;j++)
		{
			c[i][j]=((c[i-1][j-1]%k)+(c[i-1][j]%k))%k;
		    if(!c[i][j])a[i][j]=1;
		}
	}
	for(int i=1;i<=2000;i++){
		a[i][0]+=a[i-1][0];
		a[0][i]+=a[0][i-1];
		for(int j=1;j<=2000;j++)a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
	}
	for(int i=1;i<=t;i++)
	{
		long long ans=0;
		scanf("%lld%lld",&n,&m);
		cout<<a[n][m]<<endl;
	}
	fclose(stdin);fclose(stdout);
	return 0;
}