#include <cstdio>
#include <cstring>
int MOD,n,K,m;
bool hash[(1<<20)+1];
inline bool Check(int u)
{
	int sum=0,k=u;
	for (register int i=0;i<n;++i,k>>=1)
		if (k&1) sum=0;else 
		{
			if (sum==n) --sum;
			if (++sum>K) return 0;
		}
	for (register int i=0;i<n;++i,u>>=1)
		if (u&1) sum=0;else
		{
			if (sum==n) --sum;
			if (++sum>K) return 0;
		}
	return 1;
}
void slove()
{
	memset(hash,0,sizeof(hash));
	m=(1<<n);
	int i,j,k,Ans=0;
	for (i=0;i<m;++i)
		if (!hash[i])
		{
			if (Check(i)) ++Ans;
			k=i;
			for (j=0;j<n;++j)
			{
				hash[k]=1;
				k=((k&1)<<(n-1))+(k>>1);
			}
		}
	printf("%d\n",Ans%MOD);
}
int main()
{
freopen("01ring.in","r",stdin);
freopen("01ring.out","w",stdout);
	int t;
	scanf("%d%d",&t,&MOD);
	while (t--)
	{
		scanf("%d%d",&n,&K);
		slove();
	}
	return 0;
}