using namespace std;
int t,k;
int c[3010][3010];
int sum[3010][3010];
int main(){
	cin>>t>>k;
	c[1][1]=c[0][0]=c[1][0]=1;
	for(int i=2;i<=2030;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++){
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
			if(c[i][j]==0)sum[i][j]++;
		}
		sum[i][i+1]=sum[i][i];
	}
	for(int i=1;i<=t;i++){
		int n,m;
		cin>>n>>m;
		m=max(n,m);
		cout<<sum[n][m]<<endl;
	}
	return 0;
}