#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;

long t,m,k,n;
long long ans;
bool f;

void solve(long nn,long kk)
{
	long l,n2;
	n2=nn;
	if(nn%2!=0)
		nn-=1;
	if(!f)
		nn-=2;
	if(nn<kk)
		ans++;
	else
		ans+=nn/kk;
	if((kk>=2)&&(n2-kk-1>=2))
		for(l=1;l<=n2-kk-2;l++)
		{
			solve(n2-kk-1,l);
			f=true;
		}
	return;
}

int main()
{
	long  i,j;
	freopen("01ring.in","r",stdin);
	freopen("01ring.out","w",stdout);
	scanf("%d%d",&t,&m);
	for(i=1;i<=t;i++)
	{
		ans=0;
		scanf("%d%d",&n,&k);
		for(j=1;j<=k;j++)
		{
			f=false;
			solve(n,j);
		}
		ans++;
		printf("%d\n",ans%m);
	}
	return 0;
}