#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=2e3+1e3+7;

typedef long long ll;

ll c[N][N],s[N][N],n,m,T,k;

int main()
{
	freopen("problem.in","r",stdin);
	freopen("problem.out","w",stdout); 
	scanf("%d%d",&T,&k);
	for(int i=0;i<=2000;i++)
	{
		for(int j=0;j<=i;j++)
		{
			if(j==0||i==0)
				c[i][j]=1;
			else
				c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
		}
	}
	for(int i=0;i<=2000;i++)
	{
		for(int j=0;j<=2000;j++)
		{
			if(j>i)
				c[i][j]=1;
			if(i&&j)
				s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+(c[i][j]==0);
			else
			if(i)
				s[i][j]=s[i-1][j]+(c[i][j]==0);
			else
			if(j)
				s[i][j]=s[i][j-1]+(c[i][j]==0);
			else
				s[i][j]=(c[i][j]==0);
		}
	}
	while(T--)
	{
		scanf("%d%d",&n,&m);
		printf("%d\n",s[n][min(n,m)]);
	}
}