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

#define ll long long
#define ull unsigned long long
#define int ll
#define INF 0x3f3f3f3f3f3f3f3f

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);
    map<pair<int, int>, int> f;
    auto dfs = [&](auto self, int a, int c) -> int
    {
        if(a == 1)
            return 0;
        if(c == 1)
            return a - 1;
        if(f.contains({a, c}))
            return f[{a, c}];
        int ans = INF;
        for (int y : pfs)
        {
            if(c % y != 0)
                continue;
            ans = min(ans, min(self(self, a / y, c / y) + a % y, self(self, a / y + !!(a % y), c / y) + (y - a % y) % y) + 1);
        }
        // cerr << "a=" << a << " c=" << c << " ans=" << ans << endl;
        return f[{a, c}] = ans;
    };
    int ans = dfs(dfs, a, b - a);
    cout << ans << '\n';
}

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