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

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

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

ull hashp(int x, int y) {
    return x * (int)1E9 + y;
}

unordered_map<ull, int> mp;

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

    int c = abs(ca - cb);

    vector<int> fac;
    for (int i = 2; i * i <= c; i++) {
        if (c % i == 0) {
            fac.push_back(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 (b - a == 1) return a - 1;
        if (a == 1) return 0;
        if (mp.count(hashp(a, b))) return mp[hashp(a, b)];

        int ans = a - 1;
        for (int e : fac) {
            if (a % e == b % e) {
                // if (a % e <= e - a % e) {
                    ans = min(ans, 1 + a % e + dfs(a / e, b / e));
                // } else {
                    ans = min(ans, 1 + e - a % e + dfs(a / e + 1, b / e + 1));
                // }
            }
        }

        return mp[hashp(a, b)] = ans;
    };
    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);
    }
}
 

answer.code:72:1: error: extended character   is not valid in an identifier
   72 |  
      | ^
answer.code:72:1: error: ‘ ’ does not name a type
   72 |  
      | ^