# include<bits/stdc++.h>
using namespace std;
int apple (long long int m1 , long long int n1) {
	if (m1 == 0 || m1 == 1 || n1 == 1) {
		return 1;
	}
	else if (m1 < n1){
		apple (m1 , m1);
	}
	else return apple (m1 - n1 , n1) + apple (m1 , n1 - 1);
}
int main() {
	long long int m, n, b;
	cin >> b;
	for (int q = 0 ; q < b ; q++) {
		cin >> m >> n;
		cout << apple (m , n) << endl;
	}
    return 0;
}