#include <bits/stdc++.h>
using namespace std;
int pg(int m,int n)//m is pg,n is panzi
{
	if(m==1)
	  return 1;
	if(n==1)
	  return 1;
	if(m==0)
	  return 1;
	if(m<n)
	  return pg(m,m);
	else
	  return pg(m-n,n)+pg(m,n-1);
}
int main()
{
	int a,m,n,i=0;
	cin>>a;
    for(int i=0;i<=a-1;i++)
    {
    	cin>>m>>n;
        cout<<pg(m,n)<<endl;
	}
    return 0;
}