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

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;
        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;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
        q.emplace(0, a);
        while(!q.empty()){
            auto[d, u] = 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);
            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);
            }
        }
    }
    
    return 0;
}