#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        ll a, b;
        cin >> a >> b;
        vector<int> dp(a + 1, 1e9);
        using P = pair<int, int>;
        priority_queue<P, vector<P>, greater<>> pq;
        dp[gcd(a, b)] = 0;
        pq.emplace(0, gcd(a, b));
        ll res = 1e18;
        while (!pq.empty()) {
            auto [d, x] = pq.top();
            pq.pop();
            if (dp[x] < d) continue;

            ll A = a / x * x, B = b / x * x;
            res = min(res, d + A / x + 1);
            for (int i = x + x; i < dp.size(); i += x) {
                int cost = (A % i) / x + (B % i) / x;
                if (dp[i] > d + cost) {
                    dp[i] = d + cost;
                    pq.emplace(dp[i], i);
                }
            }
        }
        cout << res << "\n";
    }
}