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

#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f

void solve()
{
    int a, b;
    cin >> a >> b;
    auto getprimefact = [&](int x) -> vector<int>
    {
        vector<int> ans;
        for (int i = 2; i * i <= x; i++)
        {
            int cnt = 0;
            while (x % i == 0)
            {
                x /= i;
                cnt++;
            }
            if (cnt)
                ans.push_back(i);
        }
        if (x != 1)
            ans.push_back(x);
        return ans;
    };
    if (b < a)
        swap(a, b);
    vector<int> pfs = getprimefact(b - a);
    if (b == a)
    {
        int ans = 0;
        int x = a;
        for (auto &y : pfs)
        {
            while (x % y == 0)
            {
                ans++;
                x /= y;
            }
        }
        cout << ans << '\n';
        return;
    }

    map<pair<int, int>, int> f;
    auto dfs = [&](auto self, int d, int lt, bool bg) -> int
    {
        // cerr << "d=" << d << " lt=" << lt << endl;
        if (lt == 1)
        {
            return d;
        }
        if(f.contains({d, lt}))
            return f[{d, lt}];
        int aans = INF;
        if(1)
        {
            bool nbg = bg;
            if (d / lt)
                nbg = 1;
            int ans = nbg ? d / lt + 1 : 0;
            int tans = INF;
            int ld = d % lt;
            for (auto &y : pfs)
            {
                if (lt % y == 0)
                {
                    tans = min(tans, self(self, ld, lt / y, nbg));
                }
            }
            aans = min(aans, ans + tans);
        }
        if(d % lt > lt / 2)
        // if(1)
        {
            bool nbg = bg;
            if (d / lt + !!(d % lt))
                nbg = 1;
            int ans = nbg ? d / lt + 1 + 1 : 0;
            int tans = INF;
            int ld = lt - d % lt;
            // assert(ld >= 0);
            for (auto &y : pfs)
            {
                if (lt % y == 0)
                {
                    tans = min(tans, self(self, ld, lt / y, nbg));
                }
            }
            aans = min(aans, ans + tans);
        }
        // cerr << "d=" << d << " lt=" << lt << " ans=" << aans << endl;

        return f[{d, lt}] = aans;
    };
    int ans = dfs(dfs, a, b - a, 0);
    cout << ans - 1 << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}