#include <bits/stdc++.h>

int T, a, b;
int d[3000], p[15], divs[3000];
std::unordered_map<int, int> d1, d2;
int f[3000][1500];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> T;
    while(T--) {
        std::cin >> a >> b;
        if(a > b) std::swap(a, b);
        if(b - a == 1) {
            std::cout << a - 1 << "\n";
        } else {
            int delta = b - a, dd = delta, pi = 0, cnt = 0;
            for(int i = 2; i <= sqrt(dd); i++) {
                if(dd % i == 0) {
                    p[++pi] = i;
                    while(dd % i == 0) dd /= i;
                }
            }
            if(dd > 1) p[++pi] = dd;
            for(int i = 1; i <= sqrt(delta); i++) {
                if(delta % i == 0) {
                    d[++cnt] = i;
                    if(delta / i != i) d[++cnt] = delta / i;
                }
            }

            d1.clear();
            d2.clear();
            std::sort(d + 1, d + cnt + 1);
            for(int i = 1; i <= cnt; i++) {
                d2[d[i]] = i;
            }
            // int cnt1 = 0;
            // for(int i = cnt; i >= 1; i--) {
            //     int fl = a / d[i];
            //     int rg = a / d[i] + (a % d[i] != 0);
            //     if(fl && d1[fl] == 0) {
            //         ++cnt1;
            //         d1[fl] = cnt1;
            //         divs[cnt1] = fl;
            //     }
            //     if(rg && d1[rg] == 0) {
            //         ++cnt1;
            //         d1[rg] = cnt1;
            //         divs[cnt1] = rg;
            //     }
            //    // std::cout << fl << " " << rg << " " << d[i] << " " << cnt1 << "\n";
            // }

            memset(f, 0x7f, sizeof(f));
            f[1][0] = 0;
            for(int i = 1; i <= cnt; i++) {
                for(int j = 0; j <= 1; j++) {
                    int delt = delta / d[i];
                    if(a % d[i] == 0 && j) continue;
                    int res = a / d[i] + j;
                    for(int k = 1; k <= pi; k++) {
                        if(delta % p[k] == 0) {
                            int lf = res / p[k];
                            int rg = res / p[k] + (res % p[k] == 0);
                            int sta = a / (d[i] * p[k]);
                            int pos = d2[d[i] * p[k]];
                            if(lf != 0) {
                                f[pos][lf - sta] = std::min(f[pos][lf - sta], f[i][j] + res % p[k] + 1);
                            } 
                            if(rg != 0) {
                                f[pos][rg - sta] = std::min(f[pos][rg - sta], f[i][j] + p[k] - res % p[k] + 1);
                            }
                        }
                    }
                }
            }
            
            int ans = INT_MAX;
            for(int i = 1; i <= cnt; i++) {
                for(int j = 0; j <= 1; j++) {
                    if(a % d[i] == 0 && j) continue;
                    int res = a / d[i] + j;
                    if(res == 0) continue;
                    ans = std::min(ans, f[i][j] + res - 1);
                }
            }
            std::cout << ans << "\n";
        }
        
    }
    return 0;
}