#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e6 + 10;


void solve()
{
    int a, b; cin >> a >> b;
    if (a > b)swap(a, b);
    int d = b - a, s = d;
    vector<int>p;
    for (int i = 2; i <= d / i; i++) {
        if (d % i == 0) {
            p.push_back(i);
            while (d % i == 0)d /= i;
        }
    }
    if (d > 1)p.push_back(d);
    sort(p.begin(), p.end());
    priority_queue < pair<int, pair<int, int>>>heap;
    map<pair<int, int>, int>cnt;
    heap.push({ 0, {a, 1} });
    int res = a - 1;
    while (!heap.empty()) {
        auto q = heap.top(); heap.pop();
        int dist = -q.first, u = q.second.first, k = q.second.second;
        if (cnt.count(q.second) && cnt[q.second] <= dist || dist >= res)continue;
        if (u == 1) {
            res = min(res, dist);

            continue;
        }
        else cnt[q.second] = dist;
        for (auto d : p) {
            if (s / k % d == 0) {
                if (u % d == 0) {
                    heap.push({ -dist - 1, {u / d, k * d} });
                }
                else if (u < d) {
                    res = min(res, u - 1 + dist);
                    heap.push({ -(dist + d - u % d + 1), {u / d + 1, k * d} });
                }
                else {
                    heap.push({ -(dist + d - u % d + 1), {u / d + 1, k * d} });
                    heap.push({ -(dist + u % d + 1), {u / d, k * d} });
                }
            }
        }
    }
    cout << res << '\n';
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--)solve();
    return 0;
}