#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define int long long
#define FOR(i, j, k) for(int i = (j);i <= (k);i ++)
#define ROF(i, j, k) for(int i = (j);i >= (k);i --)
#define For(i, j, k) for(int i = (j);i < (k);i ++)
#define Rof(i, j, k) for(int i = (j);i > (k);i --)
#define ull unsigned long long
#define PII pair<int,int>
#define ULL unsigned long long
#define db double
#define x first
#define y second
#define sp(x) fixed << setprecision(x)
#define all(x) x.begin(), x.end()
#define unq_all(x) x.erase(unique(all(x)), x.end())
#define M(x) x %= mod, x += mod, x %= mod
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define Yes cout << "Yes\n"
#define No cout << "No\n"
#define ANS cout << ans << '\n'
#define de(p) cout << #p << ' ' << p << '\n'
#define END(i, n) (i == n ? '\n' : ' ')
#define double long double

#define RED cout << "\033[91m"
#define GREEN cout << "\033[92m"
#define YELLOW cout << "\033[93m"
#define BLUE cout << "\033[94m"
#define MAGENTA cout << "\033[95m"
#define CYAN cout << "\033[96m"
#define RESET cout << "\033[0m"

// 红色
#define DEBUG1(x)                     \
    RED;                              \
    cout << #x << " : " << x << endl; \
    RESET;

// 绿色
#define DEBUG2(x)                     \
    GREEN;                            \
    cout << #x << " : " << x << endl; \
    RESET;

// 蓝色
#define DEBUG3(x)                     \
    BLUE;                             \
    cout << #x << " : " << x << endl; \
    RESET;

// 品红
#define DEBUG4(x)                     \
    MAGENTA;                          \
    cout << #x << " : " << x << endl; \
    RESET;

// 青色
#define DEBUG5(x)                     \
    CYAN;                             \
    cout << #x << " : " << x << endl; \
    RESET;

// 黄色
#define DEBUG6(x)                     \
    YELLOW;                           \
    cout << #x << " : " << x << endl; \
    RESET;


using namespace std;


const int N = 1e6 + 10, M = N * 2, INF = 1e9, mod = 998244353;

int n, m, k;
int a,b;
int ans = 0;
map<PII,int> mp;
int P[N];

int get(int x,int dlt)
{
    if (x == 1)
    {
        return 0;
    }
    else if (dlt == 1)
    {
        return x - 1;
    }
    if (mp.find({x,dlt + x}) != mp.end()) return mp[{x,dlt + x}];
    mp[{x,x + dlt}] = 1e9;
    FOR(j,1,n)
    {
        int i = P[j];
        if (dlt % i == 0)
        {
            if (x % i == 0)
            {
                mp[{x,x + dlt}] = min(mp[{x,x + dlt}],get(x / i,dlt / i) + 1);
            }
            else
            {
                mp[{x,x + dlt}] =
                        min({mp[{x,x + dlt}],
                             get(x - (x % i),dlt) + (x % i),
                             get(x - (x % i) + i,dlt) - (x % i) + i});
            }
        }
    }
    return mp[{x,x + dlt}];
}

void solve()
{
    cin >> a >> b;
    if (a > b) swap(a,b);
    int dlt = b - a;

    n = 0;
    int res = dlt;
    FOR(i,2,res / i)
    {
        if (res % i == 0)
        {
            P[++n] = i;
            while (res % i == 0)
            {
                res /= i;
            }
        }
    }
    if (res != 1) P[++n] = res;
//    ans = min(ans,get(a,dlt));
    cout << get(a,dlt) << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    auto t = clock();
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    auto tt = clock();

//    cout << "Time: " << 1000.0 * (tt - t) / CLOCKS_PER_SEC << "ms" << endl;
    return 0;
}