#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;

vector<int> p;
int vis[40005];

void solve() {
    int n,m;
    cin>>n>>m;
    auto get=[&](int d){
        vector<int> tmp;
        for(int x:p){
            if(x*2>d) break;
            if(d%x==0)
            tmp.push_back(x);
        }
        if(tmp.empty()) tmp.push_back(d);
        return tmp;
    };
    map<array<int,2>,int> mp;
    function<int(int,int)> dfs=[&](int n,int m){
        int d=abs(n-m);
        if(n==1 || m==1) return 0LL;
        if(d==1) return min(n,m)-1;
        if(mp.count({n,m})) return mp[{n,m}];
        vector<int> tmp=get(d);
        int res=inf;
        for(auto x:tmp){
            if(n%x){
                int ad=n%x;
                if(ad>=100) continue;
                if(n!=ad && m!=ad) 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(n,m)<<'\n';
}

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    rep(i,2,40000){
        if(vis[i]) continue;
        p.push_back(i);
        for(int j=2;j*i<=40000;j++) vis[i*j]=1;
    }
    int tt = 1;
    cin >> tt;
    rep(kase, 1, tt) solve();
}