#include <bits/stdc++.h>

#define forp(_i) for (int _i = 0; _i < 6; ++_i)
using namespace std;

string gen_string(int64_t a, int64_t b) {
	string res;
	int ia = 0, ib = 0;
	while (ia + ib < a + b) {
		if ((__int128)ia * b <= (__int128)ib * a) {
			res += '0';
			ia++;
		} else {
			res += '1';
			ib++;
		}
	}
	return res;
}

int64_t solve(int64_t a, int64_t b) {
	if (a == b)
		return 2 * a - 1;
	if (a - b > b) {
		int64_t k = (a - b) / b;
		return k + solve(a - k * b, b);
	}
	if (a < b) {
		int64_t k = b / a;
		if (b % a == 0) --k;
		return k + solve(a, b - a * k);
	}
	return (2 * a - b - 1) / (a - b) - 1 + solve(a - b, b);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
/*	set<string> ss;
	for (int a = 1; a <= 100; ++a) {
		for (int b = 1; b <= 100; ++b) {
			ss.emplace(gen_string(a, b));
		}
	}*/

	int T;
	cin >> T;
	while (T--) {
		int64_t a, b;
		cin >> a >> b;
		cout << solve(a, b) << '\n';
	}

}