include

using namespace std;

int f(int m, int n) {

if (n <= 1 || m <= 1) {
	return 1;
}
if (m < n) {
	return f(m, m);
}
if (n == m) {
	return 1 + f(m, n-1);
}
if (n < m) {
	return f(m-n, n) + f(m,n-1);
}

}

int main() {

int t, n, m;
cin >> t;
for (int i = 0; i < t; i++) {
	cin >> m >> n;
	cout << f(m, n) << endl;
}
return 0;

}