#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) {
    ll res = 1e18;
    vector<ll> dp(a + 1, 1e18);
    dp[a] = b;
    for (int i = 0; i <= a + 2; ++i) {
        if (dp[0] == 0) {
            res = i;
            break;
        }
        vector<ll> ndp(a + 1, 1e18);
        for (int j = 0; j <= a; ++j) {
            if (dp[j] == 1e18) continue;
            ll g = gcd(j, dp[j]);
            if (0 <= j - g) ndp[j - g] = min(ndp[j - g], dp[j]);
            if (0 <= dp[j] - g) ndp[j] = min(ndp[j], dp[j] - g);
        }
        swap(dp, ndp);
    }
    return res;
}

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(30) + 1, b = myRand(30) + 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;
        //        }
        ll a, b;
        cin >> a >> b;
        cout << slv(a, b) << "\n";
    }
}