#include<stdio.h>
int f(int M,int N)
{
     if(N==1||M==1||N==0||M==0)
     return(1);
    else if(M>=N)
     return (f(M-N,N)+f(M,N-1));
    else if(M<N)
     return(f(M,M));
}
void main()
{
    int a,b,c,i;
    scanf("%d",&c);
    for(i=0;i<c;i++)
    {
        scanf("%d %d",&a,&b);
    printf("%d\n",f(a,b));
    }
}