#include <bits/stdc++.h>
const int MAXN = 1e5 + 7;
const int inf = 1e9 + 7;
using namespace std;
map <pair <int, int>, int> mp;
priority_queue <pair <int, int>, vector <pair<int, int> >, greater <pair <int, int> > > q;
int tot, dis[MAXN];
pair <int, int> opt[MAXN];
bool vis[MAXN];
void solve()
{
    int a, b;
    cin >> a >> b;
    if (a > b) swap(a, b); 
    opt.clear()
    opt[1].first = a; opt[1].second = b - a;
    for (int i = 1; i < MAXN; i++)
    {
        dis[i] = inf; vis[i] = 0;
    }
    mp.clear();
    while (!q.empty()) q.pop();
    tot = 1; dis[tot] = 0;
    mp[opt[1]] = tot;
    pair <int, int> pr = make_pair(0, 1);
    pair <int, int> tmp, to_tmp;
    pair <int, int> p, to_p;
    q.push(pr);
    int ans = inf;
    while (!q.empty())
    {
        tmp = q.top(); q.pop();
        p = opt[tmp.second];
        if (dis[tmp.second] >= ans) break;
       // cout << p.first << " " << p.second <<" " << dis[tmp.second] << '\n';
        ans = min(ans, dis[tmp.second] + p.first - 1);
        if (p.first == 1) break;
        if (vis[tmp.second]) continue;
        vis[tmp.second] = 1;
        int sss = p.second;
        for (int i = 2; i * i <= sss; i++)
        {
            if (sss % i == 0)
            {
                // -k;
                if (p.first >= i)
                {
                    to_p.first = p.first / i; to_p.second = p.second / i;
                    if (mp[to_p] == 0){
                        mp[to_p] = ++tot;
                        opt[tot] = to_p;
                    }
                    if (dis[tmp.second] + (p.first % i) + 1 < dis[mp[to_p]])
                    {
                        dis[mp[to_p]] = dis[tmp.second] + (p.first % i) + 1;
                        to_tmp = make_pair(dis[mp[to_p]], mp[to_p]);
                        q.push(to_tmp);
                    }
                }
                //+k
                to_p.first = p.first / i + 1; to_p.second = p.second / i;
                if (mp[to_p] == 0){
                    mp[to_p] = ++tot;
                    opt[tot] = to_p;
                }
                if (dis[tmp.second] + (i - p.first % i) + 1 < dis[mp[to_p]])
                {
                    dis[mp[to_p]] = dis[tmp.second] + (i - p.first % i) + 1;
                    to_tmp = make_pair(dis[mp[to_p]], mp[to_p]);
                    q.push(to_tmp);
                }
            while (sss % i == 0) sss /= i;
            }
        }
        if (sss > 1)
        {
            int i = sss;
            if (p.first >= i)
                {
                    to_p.first = p.first / i; to_p.second = p.second / i;
                    if (mp[to_p] == 0){
                        mp[to_p] = ++tot;
                        opt[tot] = to_p;
                    }
                    if (dis[tmp.second] + (p.first % i) + 1 < dis[mp[to_p]])
                    {
                        dis[mp[to_p]] = dis[tmp.second] + (p.first % i) + 1;
                        to_tmp = make_pair(dis[mp[to_p]], mp[to_p]);
                        q.push(to_tmp);
                    }
                }
                //+k
                to_p.first = p.first / i + 1; to_p.second = p.second / i;
                if (mp[to_p] == 0){
                    mp[to_p] = ++tot;
                    opt[tot] = to_p;
                }
                if (dis[tmp.second] + (i - p.first % i) + 1 < dis[mp[to_p]])
                {
                    dis[mp[to_p]] = dis[tmp.second] + (i - p.first % i) + 1;
                    to_tmp = make_pair(dis[mp[to_p]], mp[to_p]);
                    q.push(to_tmp);
                }
        }
    }
    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
 
    return 0;
}
/*
1
4237718 237821
 
*/

answer.code: In function ‘void solve()’:
answer.code:15:9: error: request for member ‘clear’ in ‘opt’, which is of non-class type ‘std::pair<int, int> [100007]’
   15 |     opt.clear()
      |         ^~~~~