#include <bits/stdc++.h>
using i64 = long long;

consteval auto operator"" _f(const char* str, std::size_t len) {
    return [fmt = std::string_view(str, len)](auto&&... args) {
        return std::vformat(fmt, std::make_format_args(args...));
    };
}

void solve() {
    i64 a, b;
    std::cin >> a >> b;

    int ans = 100;
    auto dfs = [&](auto &&self, i64 a, i64 b, int cur) -> void {
        if (a == 0 || b == 0) {
            ans = std::min(ans, cur + 1);
            return;
        }
//        if (cur > ans) return;
        i64 g = std::gcd(a, b);
        self(self, a - g, b, cur + 1);
        self(self, a, b - g, cur + 1);
    };
    dfs(dfs, a, b, 0);
    std::cout << ans << "\n";
}
signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int _ = 1;
    std::cin >> _;
    while (_ --) {
        solve();
    }
    return 0;
}