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

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

    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){
            int ans = 0;
            for(int x = 2; x * x <= a; x++){
                while(a % x == 0){
                    a /= x;
                    ans++;
                }
            }
            if(a > 1) ans++;
            cout << ans << '\n';
            continue;
        }else if(c == 1){
            cout << a - 1 << '\n';
            continue;
        }

        vector<int> fac;
        for(int x = 2; x * x <= c; x++){
            if(c % x == 0){
                fac.push_back(x);
                while(c % x == 0) c /= x;
            }
        }
        if(c > 1) fac.push_back(c);

        unordered_set<int> vis;
        using Node = tuple<int, int, int>;
        priority_queue<Node, vector<Node>, greater<>> q;
        q.emplace(0, a, b);
        while(!q.empty()){
            auto[d, u, v] = q.top(); q.pop();
            if(u == 1){
                cout << d << '\n';
                break;
            }
            if(vis.count(u)) continue;
            vis.insert(u);
            q.emplace(d + u - 1, 1, v - u + 1);
            for(auto p : fac){
                if((u - v) % p != 0) continue;
                
                auto x = u % p;
                if((u - x) / p > 0) q.emplace(d + x + 1, (u - x) / p, (v - x) / p);
                
                x = p - u % p;
                q.emplace(d + x + 1, (u + x) / p, (v + x) / p);
            }
        }
    }
    
    return 0;
}