#include <bits/stdc++.h>
using namespace std;
#define int long long


void solve() {
	int a, b;
	cin >> a >> b;
	if (a > b) {
		swap(a, b);
	}
	int t = b - a;
	vector<int>cnt;
	for (int i = 2; i <= t; i++) {
		if (t % i == 0) {
			cnt.push_back(i);
			while (t % i == 0) {
				t /= i;
			}
		}
	}
	if (t != 1) {
		cnt.push_back(t);
	}
	map<pair<int, int>, int>mp;
	int ans = a - 1;
	function<int(int, int, int)>dfs1 = [&](int a, int b, int tt) {
		if (a == 1) {
			return (int)0;
		}
		if (tt >= ans) {
			return (int)0;
		}
		if (mp[ {a, b}]) {
			return mp[ {a, b}];
		}
		mp[ {a, b}] = 1e18;
		for (int i = 0; i < cnt.size(); i++) {
			int x = a % cnt[i];
			int u;
			if (x == a) {
				u = x - 1;
				ans = min(ans, tt + x - 1);
			} else {
				u = x + 1 + dfs1((a - x) / cnt[i], (b - x) / cnt[i], tt + x + 1);
			}
			u = min(u, dfs1(((cnt[i] - x) + a) / cnt[i], ((cnt[i] - x) + b) / cnt[i], tt + cnt[i] - x + 1) + cnt[i] - x + 1);
			mp[ {a, b}] = min(mp[ {a, b}], u);
			ans = min(ans, u + tt);
		}
		return mp[ {a, b}];
	};
	dfs1(a, b, 0);
	cout << ans << endl;
	return;
}




signed main() {
	ios::sync_with_stdio(false);
	int tt = 1;
	cin >> tt;
	while (tt--) {
		solve();
	}
}