#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][2];

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;
                }
            }

            d2.clear();
            std::sort(d + 1, d + cnt + 1);
            for(int i = 1; i <= cnt; i++) {
                d2[d[i]] = i;
            }

            memset(f, 0x7f, sizeof(f));
            f[1][0] = 0;

            // f[p][0/1]:
            // delta
            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;
                    if(res <= 1) continue;
                    for(int k = 1; k <= pi; k++) {
                        if(delt % 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);
                            }
                        }
                    }
                }
            }
            
            // 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;
            //         std::cout << "f(" << d[i] << "," << res << ") = " << f[i][j] << "\n";
            //     } 
            // }
            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);
                    // if(f[i][j] + res - 1 == 12) {
                    //     std::cout << d[i] << " " << j << " " << res << " " << f[i][j] << "\n";
                    // }
                }
            }
            std::cout << ans << "\n";
        }
        
    }
    return 0;
}