#include <iostream>
using namespace std;
int dfs(int m, int n) {
if (m == 0 || n == 1) return 1;
if (m < n) return dfs(m, m);
return dfs(m, n - 1) + dfs(m - n, n);
}
int main() {
freopen("p1567.in","r",stdin);
freopen("p1567.out","w",stdout);
int t;
cin >> t;
while (t--) {
int M, N;
cin >> M >> N;
cout << dfs(M, N) << endl;
}
fclose(stdin);
fclose(stdout);
return 0;
} ( )
S
