#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 testid) {
    int ca, cb;
    cin >> ca >> cb;
    if(testid==60){
        cout<<ca<<cb<<"\n";
        return ;
    }
    int c = abs(ca - cb);

    vector<int> fac;
    // int oldc = c;
    for (int i = 2; i * i <= c; 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 {
        if (a > b) swap(a, b);
        // cout << a << " " << b << endl;
        if (a == 1) return 0;
        if(mp.count({a, b})) return mp[{a, b}];

        int res = 0;
        int cnt = INF;
        for (int e : fac) {
            int ra, rb;
            if (a % e == b % e) {
                if (a % e <= e - a % e) {
                    cnt = a % e;
                    res = e;
                    ra = a - cnt;
                    rb = b - cnt;
                } else {
                    cnt = e - a % e;
                    res = e;
                    ra = a + cnt;
                    rb = b + cnt;
                }
                // COUT(cnt);
                // COUT(res);
                // cout<<"\n";
                if (mp.count({a, b})) {
                    mp[{a, b}] = min(mp[{a, b}], 1 + cnt + dfs(ra / res, rb / res));
                } else {
                    mp[{a, b}] = 1 + cnt + dfs(ra / res, rb / 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[{1,2}]<<"*\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(CUR);
    }
}