#include <bits/stdc++.h> 
using LL = long long;

int T, a, b;

std::vector<std::pair<int, int> > fac;
void factor(int x) {
    fac.clear();
    for(int i = 2; i <= sqrt(x); i++) {
        int cnt = 0;
        while(x % i == 0) {
            x /= i;
            ++cnt;
        }
        if(cnt) fac.emplace_back(std::make_pair(i, cnt));
    }
    if(x > 1) fac.emplace_back(std::make_pair(x, 1));
}

int dfs(int x, int y) {
    if(x == 0) return 1;
    if(x == 1) return 0;
    int ans = x - 1;
    for(auto p : fac) {
        if((y - x) % p.first == 0) {
         //   std::cout << x << " " << y << " " << p.first << " " << ans << "\n";
            if(y % p.first <= p.first - y % p.first) {
                int v = y / p.first * p.first;
                int u = x / p.first * p.first;
                int cc = 0;
                //while(u > 0 && u % p.first == 0) ++cc, 
                u /= p.first, v /= p.first;
                ans = std::min(ans, y % p.first + 1 + dfs(u, v));
            } else {
                int v = (y / p.first + 1) * p.first;
                int u = (x / p.first + 1) * p.first;
                int cc = 0;
                //while(u > 0 && u % p.first == 0) ++cc, 
                u /= p.first, v /= p.first;
                ans = std::min(ans, p.first - y % p.first + 1 + dfs(u, v));
            }
        }
    } 
    return ans;
}

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 {
            factor(b - a);
            std::cout << dfs(a, b) << "\n";
        }
    }
}