//
// Created by wxy3265 on 2024/10/20.
//

#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#define int long long
using namespace std;

struct Status{
    int a, b, step;
};

const int MAXP = 1e5 + 3;
int v[MAXP], prime[MAXP];
int cnt;
void primes(int n) {
    cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (!v[i]) {
            v[i] = i;
            prime[++cnt] = i;
        }
        for (int j = 1; j <= cnt; j++) {
            if (prime[j] > v[i] || prime[j] > n / i) break;
            v[i * prime[j]] = prime[j];
        }
    }
}

int d[MAXP];
int tot;
map<pair<int, int>, int> mp;

void dfs(int a, int b) {
    if (mp.count(make_pair(a, b))) return;
    if (a - b == 1) {
        mp[make_pair(a,b)] = b - 1;
        return;
    }
    if (b == 1) {
        mp[make_pair(a, b)] = 0;
        return;
    }
    mp[make_pair(a, b)] = 1e18;
    for (int i = 1; i <= tot; i++) {
        int p = d[i];
        if ((a - b) % p == 0) {
            int step1 = b % p;
            int step2 = p - step1;
            dfs(a / p, b / p);
            mp[make_pair(a, b)] = min(mp[make_pair(a, b)], mp[make_pair(a / p, b / p)] + step1 + 1);
            int ba = ceil((double)a / (double) p), bb = ceil((double)b / (double) p);
            dfs(ba,  bb);
            mp[make_pair(a, b)] = min(mp[make_pair(a, b)], mp[make_pair(ba, bb)] + step2 + 1);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    primes(1e5);
    int t;
    cin >> t;
    while (t--) {
        mp.clear();
        int x, y;
        cin >> x >> y;
        if (x < y) swap(x, y);
        int del = x - y;
        for (int i = 1; i <= cnt && prime[i] <= del; i++) {
            if (del % prime[i] == 0) d[++tot] = prime[i];
        }
        dfs(x, y);
        cout << mp[make_pair(x, y)] << '\n';
    }
    return 0;
}