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

unordered_map<int,int> dp2;
int check(int x) {
    if (dp2.count(x))
        return dp2[x];
    int ans = 0ll;
    for(int i = 2; i * i <= x; i++) {
        while(x % i == 0) {
            ans++;
            x /= i;
        }
    }
    if(x > 1) ans++;
    dp2[x] = ans;
    return ans;
}

int c;

map<pair<int,int>, int> dp;

int dfs(int x,int f)
{
    if (x == 1)
        return 0;

    if (dp.count({x, f}))
        return dp[{x, f}];
    
    int ans = 1e9;
    int d = c / f;

    if (d == 1)
        return 1e9;


    auto fun = [&](int u)
    {
        if (u > x)
            return (int)(1e9);
        int t = x % u;
        int t2 = u - t;
        return check(u) + min(dfs((x - t) / u,f * u) + t, dfs((x + t2) / u, f * u) + t2);
    };
    for (int i = 2;i * i <= d;i++)
    {
        if (d % i == 0)
        {
            ans = min({fun(i), ans});

            while (d % i == 0)
                d /= i;
        }
    }
    if (d > 1)
        ans = min(ans, fun(d));

    dp[{x, f}] = ans;

    return ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--){
        int a, b;
        cin >> a >> b;
        if(a > b) swap(a, b);
        c = b - a;

        if(c == 0) {
            throw std::runtime_error("humorous data");
        }
        if(c == 1){
            cout << a - 1 << endl;
            continue;
        }

        dp.clear();

        cout << dfs(a, 1) << endl;
    }

    return 0;
}