#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;
int 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);
       // cout << t << endl;
        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;
                       if(dp[t / it][num / it] == 0) dp[t / it][num / it] = cost1 + cost;
                       else dp[t / it][num / it]  = min(dp[t / it][num / it], cost1 + cost);
                       if(dp[t / it][num / it + 1] == 0) 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);
                 }
            }
        }
   //     cout << num_itr << '\n';
    }

}

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();

}