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

int check(int x) {
    int ans = 0ll;
    for(int i = 2; i * i <= x; i++) {
        while(x % i == 0) {
            ans++;
            x /= i;
        }
    }
    if(x > 1) 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);
        int c = b - a;

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

        vector<int> fac;
        for(int i=2; i*i<=c; i++){
            if(c % i == 0){
                fac.push_back(i);
                while(c % i == 0) c /= i;
            }
        }
        if(c > 1) fac.push_back(c);
        sort(fac.begin(), fac.end());
        c = b - a;

        // unordered_map<int, int> rcd;
        // rcd[1] = 0; rcd[0] = 1e9;
        // auto dfs = [&](auto&&dfs, int a)->int{
        //     if(rcd.count(a)) return rcd[a];
        //     int ans = a - 1;
        //     for(auto p : fac){
        //         auto x = a % p;
        //         ans = min(ans, dfs(dfs, a/p) + a % p + 1);
        //         if(a % p > 0){
        //             ans = min(ans, dfs(dfs, a/p + 1) + p - a % p + 1);
        //         }
        //     }
        //     // cout << format("rcd[{}] = {}\n", a, ans);
        //     return rcd[a] = ans;
        // };
        // cout << dfs(dfs, a) << '\n';

        unordered_set<int> vis;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
        q.emplace(0 ,a);
        int ans = 0x7ffffffffffll;
        while(!q.empty()){
            auto [d, u] = q.top(); q.pop();
            if(u == 0) {
                throw std::runtime_error("humorous code");
            }
            if(d >= ans) {
                break;
            } else {
                ans = std::min(ans, d + u - 1);
            }
            if(u == 1) {
                break;
            }
            if(vis.count(u)) continue;
            vis.insert(u);
            for(auto p : fac){
                if(u >= p) {
                    q.emplace(d + u % p + 1, u / p);
                }
                q.emplace(d + p - u % p + 1, u / p + 1);
            }
        }
        cout << ans << endl;
    }

    return 0;
}