#include <bits/stdc++.h>
#include <unordered_map>
using i80 = __int128;
using i64 = long long;
using f80 = long double;
constexpr i64 p = 2e9 + 1;
constexpr int N = 1e3;
std::vector<int> pm, isp(N);
std::unordered_map<i64, int> map;
void work() {
    auto chmin = [](int& x, int y) {
        if (y < x) {
            x = y;
        }
    };
    int a, b, c;
    std::cin >> a >> b;
    if (a > b) {
        std::swap(a, b);
    }
    c = b - a;
    std::vector<std::array<int, 2>> d;
    for (int i = 1; pm[i] * pm[i] <= c; ++i) {
        if (c % pm[i]) {
            continue;
        }
        int k = 0;
        while (c % pm[i] == 0) {
            ++k;
            c /= pm[i];
        }
        d.push_back({pm[i], k});
    }
    if (c > 1) {
        d.push_back({c, 1});
    }
    int n = d.size();
    std::function<int(int, int)> dfs = [&](int x, int y) {
        if (x == 1) {
            return 0;
        }
        if (map.count(x * p + y)) {
            return map[x * p + y];
        }
        int ans = x - 1;
        for (int i = 0; i < n; ++i) {
            if (d[i][1] == 0) {
                continue;
            }
            int k = x % d[i][0];
            --d[i][1];
            chmin(ans, dfs((x + k) / d[i][0], (y + k) / d[i][0]) + d[i][0] - k + 1);
            chmin(ans, dfs((x - k) / d[i][0], (y - k) / d[i][0]) + k + 1);
            ++d[i][1];
        }
        // for (int i = 0; i < n; ++i) {
        //     std::cout << "{" << d[i][0] << "," << d[i][1] << "}";
        // }
        // std::cout << x << "," << y << ":" << ans << "\n";
        return map[x * p + y] = ans;
    };
    std::cout << dfs(a, b) << "\n";
    return;
}
void init() {
    pm = {1};
    for (int i = 2; i < N; ++i) {
        if (!isp[i]) {
            pm.push_back(i);
        }
        for (int j = 1; j < (int)pm.size() && i * pm[j] < N; ++j) {
            isp[i * pm[j]] = true;
            if (i % pm[j] == 0) {
                break;
            }
        }
    }
}
int main() {
    init();
    std::ios::sync_with_stdio(false);
    // std::cin.tie(nullptr), std::cout.tie(nullptr);
    int t = 1;
    std::cin >> t;
    while (t--) {
        work();
    }
    return 0;
}
/*


*/