#include <bits/stdc++.h>
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define dbg(...) (void)0
#endif
using u32 = unsigned int;
using i64 = long long;

namespace skadi {

std::vector<i64> getd(i64 x) {
    std::vector<i64> d;
    for (i64 i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            d.push_back(i);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) d.push_back(x);
    return d;
}

void solve() {
    i64 a, b;
    std::cin >> a >> b;
    if (a > b) std::swap(a, b);
    i64 delta = b - a;
    std::vector<i64> d = getd(delta);
    std::map<std::pair<i64, i64>, i64> cnt;

    auto dfs = [&](auto&& self, i64 x, i64 delta) -> i64 {
        if (x == 1) return 0;
        if (cnt.count({x, delta})) return cnt[{x, delta}];
        if (delta == 1) return cnt[{x, delta}] = x - 1;
        i64 min = 1e9;
        for (i64 p : d) {
            if (delta % p != 0) continue;
            i64 l = x % p;
            i64 a = l + 1 + self(self, x / p, delta / p);
            i64 b = p - l + 1 + self(self, (x + p - 1) / p, delta / p);
            min = std::min({min, a, b});
        }
        return cnt[{x, delta}] = min;
    };

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

} // namespace skadi

int main() {
#ifndef LOCAL_DEBUG
    std::cin.tie(nullptr)->sync_with_stdio(false);
#endif
    int t = 1;
    std::cin >> t;
    while (t--) {
        skadi::solve();
    }
    return 0;
}