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

int n,a,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>>a;
	while(a--){
		cin>>n>>m;
		cout<<f(n,m)<<endl;
	}
	return 0;
}