#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 10005;
int pri[N], tot, fac[N];
bool not_pri[N];

void init()
{
    not_pri[1] = 1;
    for (int i = 2; i < N; ++i)
    {
        if (!not_pri[i])
        {
            pri[++tot] = i;
            fac[i] = i;
        }
        for (int j = 1; j <= tot and i * pri[j] < N; ++j)
        {
            not_pri[pri[j] * i] = 1;
            fac[i * pri[j]] = pri[j];
            if (i % pri[j])
                break;
        }
    }
}
void solve()
{
    int x, y;
    std::cin >> x >> y;
    int g = std::gcd(x, y);
    if (x > y)
    {
        std::swap(x, y);
    }
    x /= g, y /= g;
    int curx = x, cury = y;
    int ans = x + 1;
    map<pair<int, int>, int> mp;

    auto cal = [&](auto &cal, int a, int b) -> int
    {
        if (mp[{a, b}])
        {
            return mp[{a, b}];
        }

        if (a == 1)
            return mp[{a, b}] = 2;
        if (a == 0)
        {
            return mp[{a, b}] = 1;
        }
        int &now = mp[{a, b}];
        now = 1e5;
        int cur = a, add = b - a, tb = a, ta = a;
        while (cur > 1)
        {
            int t = fac[cur];
            while (cur % t == 0)
                cur /= t;
            if (b % t < add)
            {
                add = b % t;
                tb = (b - add);
            }
        }

        int g = gcd(ta, tb);
        tb /= g, ta /= g;
        now = min(now, cal(cal, ta, tb) + add);

        ta = a - 1, tb = b;
        g = gcd(ta, tb);

        ta /= g, tb /= g;

        now = min(now, cal(cal, ta, tb) + 1);
        return now;
    };
    // return cal(cal, x, y);
    cout << cal(cal, x, y) << '\n';
}
signed main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    // std::solve(6, 1) << '\n';
    init();

    // for (int i = 1; i <= 10; ++i)
    // {
    //     for (int j = 1; j <= 10; ++j)
    //     {
    //         std::cout << solve(i, j) << " \n"[j == 10];
    //     }
    // }
    int t;
    std::cin >> t;
    while (t--)
    {
        solve();
    }
}