#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int T,n,m;
int solve(int m,int n){//m个苹果 n个盘子 
    if(m<=1||n<=1) return 1;//边界条件 
    if(m<n) return solve(m,m);//苹果比盘子少 等价于把m个苹果放入m个盘子的方案数 
    else return solve(m,n-1)+solve(m-n,n);
    /*否则 等于有一个盘子空着不放的方案(有空盘) + 
    把所有盘子都铺上一层苹果后用剩下的苹果放盘子的方案(没有空盘)*/
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&m,&n);
        printf("%d\n",solve(m,n));
    }
    return 0;
}

POJ1664 放苹果