#include<iostream>
using namespace std;
int split(int n,int m){
	if(n==0||m==0)
		return 0;
	if(n==1||m==1)
		return 1;
	if(n<m) 
		return split(n,n);
	if(n==m)
		return (split(n,m-1)+1);
	return split(n,m-1)+split(n-m,m);
}
int main(){
	int n,m,a;
	cin>>a;
	while(a--){
		cin>>n>>m;
		split(n,m);
		cout<<split(n,m)<<endl;
	}
}