#include<bits/stdc++.h>
using namespace std;

int n,t,m;

int f(int n,int m){
	if(n==0||m==1)return 1;
	if(n>=m)return f(n,m-1)+f(n-m,m);
	return f(n,n); 
}

int main(){
	cin>>t;
	while(t--){
		cin>>n>>m;
		cout<<f(n,m)<<endl;
	}
	return 0;
}