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

#define pb push_back

const ld pi = 3.14159265358979323846;
const int mod = (int)1e9 + 7;
const ll INF = 1e18;

template<typename T>
T chmax(T a, T b){
    return a > b ? a : b;
}

template<typename T>
T chmin(T a, T b){
    return a > b ? b : a;
}

const int N = (int)2e5 + 1, M = N * 2;

void solve(){
    map<pair<int, int>, int> mp;

    ll a, b, qwq = (int)1e9;
    cin >> a >> b;

    auto dfs = [&](auto& self, ll x, ll y, ll z) -> void{
        if(x == 0 || y == 0){
            qwq = chmin(qwq, z + 1);
            mp[{x, y}] = z + 1;
            return;
        }
        if(mp[{x, y}] && z >= mp[{x, y}]){
            return;
        }
        mp[{x, y}] = z;

        ll gcd = __gcd(x, y);
        x /= gcd, y /= gcd;
        self(self, x - 1, y, z + 1);
        self(self, x, y - 1, z + 1);
    };

    dfs(dfs, a, b, 0);
    cout << qwq << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    cin >> t;

    while(t--){
        solve();    
    }
    return 0;
}