#include <bits/stdc++.h>

#define int long long

std::map<std::pair<int, int>, int> mp;

void solve()
{
    int x, y;
    std::cin >> x >> y;
    auto calc = [&](auto calc, int x, int y) -> int
    {
        if (x > y)
        {
            std::swap(x, y);
        }
        if (mp[{x, y}])
        {
            return mp[{x, y}];
        }
        int gcd = std::gcd(x, y);
        x /= gcd, y /= gcd;
        if (x == 1)
        {
            return 2;
        }
        if (!x and !y)
        {
            return 0;
        }
        if (!x or !y)
        {
            return 1;
        }
        int ans = 1e18;
        for (int i = 2; i <= x; ++i)
        {
            int time = x % i + y % i;
            int nx = x - x % i;
            int ny = y - y % i;
            ans = std::min(ans, calc(calc, nx, ny) + time);
        }
        mp[{x, y}] = ans;
        return ans;
    };
    std::cout << calc(calc, x, y) << '\n';
}
signed main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t;
    std::cin >> t;
    while (t--)
    {
        solve();
    }
}