#include <bits/stdc++.h>
#pragma GCC optimize (3)
#define de(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
#define lowbit(x) ((x) & (-x))
// #define int long long
#define siz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define PII pair<int, int>
using ll  = long long;
using ull = unsigned long long;
using namespace std;
constexpr ll inf = 1e18;
constexpr int N = 1e6 + 10;

std::map<std::pair<int, int>, int> mp;

void solve(int Case) {
	int a, b;
    std::cin >> a >> b;
    if (a < b) std::swap(a, b);

    int d = a - b, ans = b - 1;

    if (d == 1) {
        std::cout << ans << '\n';
        return;
    }

    std::vector<int> h;
    for (int i = 2; i * i <= d; i++) {
        if (d % i == 0) {
            h.push_back(i);
            while (d % i == 0) d /= i;       
        }
    }
    if (d != 1) h.push_back(d);

    // std::cout << "\n-----------0----------\n";
    // for (auto it : h) {
    //     std::cout << it << ' ';
    // }
    // std::cout << "\n-----------1----------\n";

    auto dfs = [&](auto &dfs, int na, int nb) -> int {
        if (na == 1 || nb == 1) {
            return 0;
        }
        if (mp.count({na, nb})) {
            return mp[{na, nb}];
        }
        int ans = 1e9;
        for (auto p : h) {
            if (abs(na - nb) % p) continue;
            int la = na - na % p, lb = nb - nb % p, ld = abs(la - na);
            int ra = la + p, rb = lb + p, rd = abs(ra - na);
            ans = std::min(ld + dfs(dfs, la / p, lb / p) + 1, ans);
            ans = std::min(rd + dfs(dfs, ra / p, rb / p) + 1, ans);
        }
        mp[{na, nb}] = ans;
        return ans;
    };

    std::cout << dfs(dfs, a, b) << '\n';
}   

signed main() {
    cin.tie(0)->ios::sync_with_stdio(false);
    int T = 1;
    cin >> T; cin.get();

    int Case = 0;
    while (++Case <= T) {
        solve(Case);
    }

    return 0;
}