#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 P = 998244353;
i64 mul(i64 a, i64 b, i64 m) {
    return static_cast<__int128>(a) * b % m;
}
i64 power(i64 a, i64 b, i64 m) {
    i64 res = 1 % m;
    for (; b; b >>= 1, a = mul(a, a, m))
        if (b & 1)
            res = mul(res, a, m);
    return res;
}
bool isprime(i64 n) { // Miller-Rabin
    if (n < 2) return false;
    static constexpr int B[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
    for (int p : B) {
        if (n == p) return true;
        if (n % p == 0) return false;
    }
    i64 m = (n - 1) >> __builtin_ctz(n - 1);
    for (int p : B) {
        i64 t = m, a = power(p, m, n);
        while (t != n - 1 && a != 1 && a != n - 1) {
            a = mul(a, a, n);
            t *= 2;
        } 
        if (a != n - 1 && t % 2 == 0) return false;
    }
    return true;
}
vector<i64> factorize(i64 n) { // Pollard-Rho
    vector<i64> p;
    function<void(i64)> f = [&](i64 n) {
        if (n <= 10000) {
            for (int i = 2; i * i <= n; i++) 
                for ( ; n % i == 0; n /= i)
                    p.push_back(i);
            if (n > 1) 
                p.push_back(n);
            return;
        }
        if (isprime(n)) {
            p.push_back(n);
            return;
        }
        auto g = [&](i64 x) {
            return (mul(x, x, n) + 1) % n;
        };
        i64 x0 = 2;
        while (true) {
            i64 x = x0, y = x0;
            i64 d = 1, pow = 1, lam = 0, v = 1;
            while (d == 1) {
                y = g(y);
                ++lam;
                v = mul(v, abs(x - y), n);
                if (lam % 127 == 0) {
                    d = gcd(v, n);
                    v = 1;
                }
                if (pow == lam) {
                    x = y;
                    pow *= 2;
                    lam = 0;
                    d = gcd(v, n);
                    v = 1;
                }
            }
            if (d != n) {
                f(d);
                f(n / d);
                return;
            }
            ++x0;
        }
    };
    f(n);
    sort(p.begin(), p.end());
    return p;
}
int f(int x) {
    return factorize(x).size();
} 
void solve() {
    int a, b;
    cin >> a >> b;
    if (a > b) swap(a, b);
    if (b % a == 0) {
        int p = f(a);
        cout << p << '\n';
        return;
    }
    b -= a;
    int g = gcd(a, b);
    int ans = 1e9;
    for (int i = 1; i * i <= g; i++) {
        if (b % i == 0) {
            int aa = a / i, bb = b / i;
            int tmp = f(i), k = bb / aa;
            if (k == 0) {
                tmp += aa - bb;
                tmp += f(bb);
            } else {
                tmp += min(bb / k - aa + f(bb / k), aa - bb / (k + 1) + f(bb / (k + 1)));
            }
            ans = min(ans, tmp);
        }
        if (i * i != b) {
            int aa = a / i, bb = b / i;
            int tmp = f(i), k = bb / aa;
            if (k == 0) {
                tmp += aa - bb;
                tmp += f(bb);
            } else {
                tmp += min(bb / k - aa + f(bb / k), aa - bb / (k + 1) + f(bb / (k + 1)));
            }
            ans = min(ans, tmp);
        }
    }
    cout << ans << '\n';
}
int main() {
    // ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int t = 1; 
    cin >> t;
    while(t--) solve();
    return 0;
}