#include<bits/stdc++.h>	
#define int long long
using namespace std;
int t,k,C[2005][2005],x[2005],y[2005];
struct node{
	int x,y;
}a[10005];
map<pair<int,int>,int> v;
bool cmp(node a,node b){
	if(a.x==b.x){
		return a.y<b.y;
	}
	return a.x<b.x;
}
signed main(){
	cin>>t>>k;
	for(int i=1;i<=t;i++){
		cin>>a[i].x>>a[i].y;
		x[i]=a[i].x;
		y[i]=a[i].y;
	}
	sort(a+1,a+t+1,cmp);
	for(int i=1;i<=2000;i++){
		C[i][0]=C[0][i]=1;
	}
	C[1][1]=1;
	int s=1,sum=0;
	for(int i=2;i<=2000;i++){
		for(int j=0;j<=i;j++){
			if(j==0){
				C[i][j]=C[i-1][j];
			}else{
				C[i][j]=(C[i-1][j-1]+C[i-1][j])%k;	
			}
			if(C[i][j]==0){
				sum++;
			}
			if(i==a[s].x&&j==a[s].y){
				v[{i,j}]=sum;
				s++;
				if(s==t+1){
					goto stop;
				}
			}else if(i==a[s].x&&a[s].y>i&&j==i){
				v[{i,a[s].y}]=sum;
				s++;
				if(s==t+1){
					goto stop;
				}
			}
			if(a[s].x==1){
				v[{a[s].x,a[s].y}]=0;
				s++;
				if(s==t+1){
					goto stop;
				}
			}
		}
	}
	stop:
	for(int i=1;i<=t;i++){
		cout<<v[{x[i],y[i]}]<<"\n";
	}
	return 0;
}