#include "stdio.h"

int DFS(int n,int m);

int main()

{

	int T;

	int n,m;

	int s;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%d",&m,&n);

		s=DFS(m,n);

		printf("%d\n",s);

	}

	return 0;

}

int DFS(int m,int n)

{

	if(m<0)

		return 0;

	if(m==0 || m==1 || n==1)

		return 1;

	return DFS(m-n,n)+DFS(m,n-1);

}