#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
const int mod = 1e9;
int __t = 1, n, a, b, tag[N];
vector<int> prime;
unordered_map<int, int> mp;
int dfs(int x, int y) {
    int z = x - y, xy = x * mod + y;
    if (x == 1 || y == 1)
        return mp[xy] = 0;
    if (mp.find(xy) != mp.end())
        return mp[xy];
    if (z == 1)
        return mp[xy] = y - 1;
    int ans = y - 1;
    for (auto p : prime) {
        if (z < p)
            break;
        if (z % p == 0) {
            int xp1 = x % p, xp2 = p - xp1;
            ans = min(ans, dfs((x - xp1) / p, (y - xp1) / p) + 1 + xp1);
            ans = min(ans, dfs((x + xp2) / p, (y + xp2) / p) + 1 + xp2);
        }
    }
    return mp[xy] = ans;
}
void solve() {
    cin >> a >> b;
    if (a < b)
        swap(a, b);
    dfs(a, b);
    cout << mp[a * mod + b] << "\n";
    return;
}
int32_t main() {
#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    for (int i = 2; i <= 1e5; i++) {
        if (tag[i])
            continue;
        prime.push_back(i);
        for (int j = i * i; j <= 1e5; j += i)
            tag[j] = 1;
    }
    cin >> __t;
    while (__t--)
        solve();
    return 0;
}