#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 P = 998244353;
const i64 B = 1e9 + 7;
i64 mul(i64 a, i64 b, i64 m) {
    return static_cast<__int128>(a) * b % m;
}
i64 power(i64 a, i64 b, i64 m) {
    i64 res = 1 % m;
    for (; b; b >>= 1, a = mul(a, a, m))
        if (b & 1)
            res = mul(res, a, m);
    return res;
}
bool isprime(i64 n) { // Miller-Rabin
    if (n < 2) return false;
    static constexpr int B[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
    for (int p : B) {
        if (n == p) return true;
        if (n % p == 0) return false;
    }
    i64 m = (n - 1) >> __builtin_ctz(n - 1);
    for (int p : B) {
        i64 t = m, a = power(p, m, n);
        while (t != n - 1 && a != 1 && a != n - 1) {
            a = mul(a, a, n);
            t *= 2;
        } 
        if (a != n - 1 && t % 2 == 0) return false;
    }
    return true;
}
vector<i64> factorize(i64 n) { // Pollard-Rho
    vector<i64> p;
    function<void(i64)> f = [&](i64 n) {
        if (n <= 10000) {
            for (int i = 2; i * i <= n; i++) 
                for ( ; n % i == 0; n /= i)
                    p.push_back(i);
            if (n > 1) 
                p.push_back(n);
            return;
        }
        if (isprime(n)) {
            p.push_back(n);
            return;
        }
        auto g = [&](i64 x) {
            return (mul(x, x, n) + 1) % n;
        };
        i64 x0 = 2;
        while (true) {
            i64 x = x0, y = x0;
            i64 d = 1, pow = 1, lam = 0, v = 1;
            while (d == 1) {
                y = g(y);
                ++lam;
                v = mul(v, abs(x - y), n);
                if (lam % 127 == 0) {
                    d = gcd(v, n);
                    v = 1;
                }
                if (pow == lam) {
                    x = y;
                    pow *= 2;
                    lam = 0;
                    d = gcd(v, n);
                    v = 1;
                }
            }
            if (d != n) {
                f(d);
                f(n / d);
                return;
            }
            ++x0;
        }
    };
    f(n);
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    return p;
}
void solve() {
    i64 a, b;
    cin >> a >> b;
    if (a > b) swap(a, b);
    b -= a;
    auto p = factorize(b);
    unordered_map<i64, i64> mp;
    auto dfs = [&](auto self, i64 x, i64 y) -> i64 {
        if (x == 1) return 0;
        if (y == 1) return x - 1;
        if (mp.count(x * B + y)) {
            return mp[x * B + y];
        }
        i64 res = 1e9;
        for (auto it : p) {
            if (y % it == 0) {
                res = min(res, self(self, x / it, y / it) + x % it + 1);
                res = min(res, self(self, x / it + 1, y / it) + it - x % it + 1);
            }
        }
        return mp[x * B + y] = res;
    };
    cout << dfs(dfs, a, b) << '\n';
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int t = 1; 
    cin >> t;
    while(t--) solve();
    return 0;
}