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

using namespace std;
int mod,n,k,T;
int f[101][101][101];
void init()
{
	scanf("%d%d",&n,&k);
	memset(f,-1,sizeof(f));
}

inline void MOD(int &x)
{
	x = x >= mod ?x-mod : x;
	x = x < 0 ? x+mod : x; 
}

int dfs(int u,int limi,int limj)
{
	if (limi>k) return 0;
	if (u==0) return 1;
	if (u<=100 && limi<=100 && limj<=100)
	{
		if (f[u][limi][limj]!=-1) return f[u][limi][limj];
		f[u][limi][limj]=0;
		for (int j=limj;limi+j<=u;j++)
		{
			f[u][limi][limj]+=dfs(u-limi-j,limi,j);
			MOD(f[u][limi][limj]);
		}
	
		int t=min(k,u-1);
		for (int i=limi+1;i<=t;i++)
		for (int j=1;i+j<=u;j++)
		{
			f[u][limi][limj]+=dfs(u-i-j,i,j);
			MOD(f[u][limi][limj]);
		}
		return f[u][limi][limj];
	}
	else
	{
		int re=0;
		for (int j=limj;limi+j<=u;j++)
		{
			re+=dfs(u-limi-j,limi,j);
			MOD(re);
		}
	
		int t=min(k,u-1);
		for (int i=limi+1;i<=t;i++)
		for (int j=1;i+j<=u;j++)
		{
			re+=dfs(u-i-j,i,j);
			MOD(re);
		}
		return re;
	}
}

void solve()
{
	
	printf("%d\n",dfs(n,1,1) + 1 + (k>=n ? 1 : 0));
}

int main()
{
	freopen("01ring.in","r",stdin);
	freopen("01ring.out","w",stdout);
	int T;
	scanf("%d%d",&T,&mod);
	for (;T;--T)
	{
		init();
		solve();
	}
	return 0;
}