#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mk make_pair
#define S second
#define F first
map<int, int> fact;
vector<int> d;
int a, b;
int num_itr = 0;
int ans;
void DP() {
    unordered_map<int, map<int, int>> dp;
    set<int> q;
    q.insert(b - a);
    dp[b - a][a] = 0;

    while (!q.empty()) {
        auto itr = q.end();
        itr--;
        int t = *itr;
        q.erase(itr);

        for (auto &[num, cost] : dp[t]) {
            ans = min(ans, num - 1 + cost);
        }

        for (int it : d) {
            if (t % it == 0) {
                for (auto &[num, cost] : dp[t]) {
                    int cost1 = num % it + 1;
                    int cost2 = it - (num % it) + 1;

                    // Update dp[t / it][num / it]
                    if (!dp[t / it].count(num / it)) {
                        dp[t / it][num / it] = cost1 + cost;
                    } else {
                        dp[t / it][num / it] = min(dp[t / it][num / it], cost1 + cost);
                    }

                    // Update dp[t / it][num / it + 1]
                    if (!dp[t / it].count(num / it + 1)) {
                        dp[t / it][num / it + 1] = cost2 + cost;
                    } else {
                        dp[t / it][num / it + 1] = min(dp[t / it][num / it + 1], cost2 + cost);
                    }

                    q.insert(t / it);
                }
            }
        }
    }
}


void solve(){
    ans = 1e9;
	cin >> a >> b;
	if(a > b) swap(a, b);
	int dif = b - a;
	if(a == 1 || b == 1){
        cout << "0\n";
        return;
	}
	if(dif == 0){
        cout << "1\n";
        return;
	}
	for(int i = 2; i * i <= dif; i++){
         while(dif % i == 0) fact[i]++, dif /= i;
	}
	if(dif > 1) fact[dif]++;
	for(auto it : fact) d.push_back(it.F);
	DP();
	cout << ans << '\n';
}
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();

}