#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;
 
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 ct) -> void {
        if (na == 0 || nb == 0) {
            return;
        }
        if (na == 1 || nb == 1) {
            ans = std::min(ans, ct);
            return;
        }


        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);
            if (ld < rd) {
                dfs(dfs, la / p, lb / p, ct + ld + 1);
            }
            else {
                dfs(dfs, ra / p, rb / p, ct + ld + 1);
            }
        }
    };

    dfs(dfs, a, b, 0);

    std::cout << ans << '\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;
}