#include <bits/stdc++.h>

using namespace std;
#define int long long
#define rep(i, a, b) for(int i=(a);i<=(b);++i)
#define sz(x) (int)x.size()
#define endl "\n"
const int N = 2e5, mod = 1e9 + 7, inf = 1e18;


void solve() {
    int nn,mm;
    cin>>nn>>mm;
    int d=abs(nn-mm);
    vector<int> tmp;
    for(int i=2;i<=sqrt(d);i++){
        if(d%i==0){
            tmp.push_back(i);
            while(d%i==0) d/=i;
        }
    }
    if(tmp.empty()) tmp.push_back(d);

    map<array<int,2>,int> mp;
    function<int(int,int)> dfs=[&](int n,int m){
        if(n==1 || m==1) return 0LL;
        if(abs(n-m)==1) return min(n,m)-1;
        if(mp.count({n,m})) return mp[{n,m}];
        int res=max(n,m)-1;
        for(auto x:tmp){
            if(abs(n-m)%x==0){
                if(n%x){
                    int ad=n%x;
                    res=min(res,1+ad+dfs((n-ad)/x,(m-ad)/x));
                    res=min(res,1+x-ad+dfs((n+x-ad)/x,(m+x-ad)/x));
                }
                else{
                    res=min(res,1+dfs(n/x,m/x));
                }
            }

        }
        mp[{n,m}]=res;
        return res;
    };

    cout<<dfs(nn,mm)<<'\n';
}

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

    int tt = 1;
    cin >> tt;
    rep(kase, 1, tt) solve();
}