#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
    i64 a, b;
    cin >> a >> b;
    const int ti = 20;
    int ans = 30;
    function<void(i64,i64,int)> dfs = [&](i64 x,i64 y, int step) {
        if (x == 0 || y == 0) {
            ans = min(ans, step);
            return;
        }
        if (step >= ti) {
            return;
        }
        i64 g = gcd(x, y);
        dfs(x - g, y, step + 1);
        dfs(x, y - g, step + 1);
        return;
    };
    dfs(a, b, 0);
    cout << ans << "\n";
    return;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}