#include<iostream>
#include<cstdio>
using namespace std;
int n,m,t;
int deal(int x,int y){
	if(x==0||y==1||x==1) return 1;
	if(y>=x) return deal(x,x);
	if(x>y) return deal(x-y,y)+deal(x,y-1);
}
int main(){
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>m>>n;
		cout<<deal(m,n);
	}
	return 0;
}