#include <cstdio>
#include <set>
using namespace std;

int N,K,re;
bool check(const int &p)
{
	if (p==0)
		return false;
	int j=0;
	for(int i=0;i<N;i++)
		if (p&(1<<i))
			j=0;
		else
		{
			j++;
			if (j>K)
				return false;
		}
	for(int i=0;i<N;i++)
		if (p&(1<<i))
			break;
		else
		{
			j++;
			if (j>K)
				return false;
		}
	return true;
}

set<int> hash;
int main()
{
	freopen("01ring.in","r",stdin);
	freopen("01ring.out","w",stdout);
	int T,MO;
	scanf("%d%d",&T,&MO);
	while(T--)
	{
		scanf("%d%d",&N,&K);
		if (K==0)
		{
			printf("1\n");
			continue;
		}
		hash.clear();
		re=0;
		for(int i=0;i<(1<<N);i++)
			if (K>=N || check(i))
			{
				int small=i,k=i;
				for(int j=1;j<N;j++)
				{
					k=(k>>1)+((k&1)<<(N-1));
					if (k<small)
						small=k;
				}
				if (!hash.count(small))
				{
					re++;
					hash.insert(small);
				}
			}
		printf("%d\n",re);
	}
}