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

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }

ll slv(ll a, ll b) {
    vector<ll> dp(a + 1, 2e18);
    {
        ll g = gcd(a, b);
        dp[a / g] = b / g;
    }
    for (int i = 0;; ++i) {
        if (dp[0] == 0) {
            return i;
        }
        vector<ll> ndp(a + 1, 2e18);
        for (int j = 0; j <= a; ++j) {
            if (dp[j] == 2e18) continue;
            if (j == 0) return i + 1;
            if (dp[j] == 0) return i + 1;
            if (0 <= j - 1) {
                ll gg = gcd(j - 1, dp[j]);
                ndp[(j - 1) / gg] = min(ndp[(j - 1) / gg], dp[j] / gg);
            }
            if (0 <= dp[j] - 1) {
                ll gg = gcd(j, dp[j] - 1);
                ndp[j / gg] = min(ndp[j / gg], (dp[j] - 1) / gg);
            }
        }
        swap(dp, ndp);
    }
    assert(false);
}

ll slv_g(ll a, ll b) {
    auto dfs = [&](auto dfs, ll x, ll y) -> ll {
        if (x == 0 and y == 0) return 0;
        if (x == 0 or y == 0) return 1;
        ll g = gcd(x, y);
        ll res = min(dfs(dfs, x - g, y) + 1, dfs(dfs, x, y - g) + 1);
        return res;
    };
    return dfs(dfs, a, b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        //        int a = myRand(50) + 1, b = myRand(50) + 1;
        //        ll res1 = slv(a, b);
        //        ll res2 = slv_g(a, b);
        //        if (res1 != res2) {
        //            cout << "a = " << a << ", b = " << b << endl;
        //            cout << "res1 = " << res1 << ", res2 = " << res2 << endl;
        //            return 0;
        //        } else {
        //            cout << "OK" << endl;
        //        }
        ll a, b;
        cin >> a >> b;
        cout << slv(a, b) << "\n";
    }
}