#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include "_my_utils.h"
#endif
#define int long long

using namespace std;
using ll = long long;
using PII = std::pair<int, int>;

constexpr ll INF = 2E18 + 10;
constexpr int N = 2E6 + 10;

map<PII, int> mp;

void SINGLE_TEST() {
    int ca, cb;
    cin >> ca >> cb;

    int c = abs(ca - cb);

    vector<int> fac;
    int oldc = c;
    for (int i = 2; i * i <= oldc; i++) {
        if (c % i == 0) {
            fac.push_back(i);
            // if (i * i != oldc) fac.push_back(oldc / i);
            while (c % i == 0) c /= i;
        }
    }
    if (c != 1) fac.push_back(c);
    sort(fac.begin(), fac.end(), greater<>());
    // debug(fac);
    function<int(int, int)> dfs = [&](int a, int b) -> int {
        // cout << a << " " << b << endl;
        if (a == 1 || b == 1) return 0;
        if (mp.count({a, b})) return mp[{a, b}];
        if (mp.count({b, a})) return mp[{b, a}];

        int res = 0;
        int cnt = INF;
        for (int e : fac) {
            if (a % e == b % e) {
                if (a % e <= e - a % e) {
                    cnt = a % e;
                    res = e;
                } else {
                    cnt = e - a % e;
                    res = e;
                }
                if (mp.count({a, b})) {
                    mp[{a, b}] =
                        min(mp[{a, b}], 1 + cnt + dfs(a / res, b / res));
                } else {
                    mp[{a, b}] = 1 + cnt + dfs(a / res, b / res);
                }
            }
        }
        if (mp.count({a, b})) {
            mp[{a, b}] = min(mp[{a, b}], min(a, b) - 1);
        } else {
            mp[{a, b}] = min(a, b) - 1;
        }
        return mp[{a, b}];
    };
    // cout<<mp[{2,6}]<<"\n";
    cout << dfs(ca, cb) << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int SAMPLES = 1;
    cin >> SAMPLES;
    for (int CUR = 1; CUR <= SAMPLES; CUR++) {
        SINGLE_TEST();
    }
}