#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);
	}
	int ans = a - 1;
	function<void(int, int, int)>dfs1 = [&](int a, int b, int tt) {
		if (tt >= ans) {
			return;
		}
		if (a == 1) {
			ans = min(ans, tt);
			return;
		}
		for (int i = 0; i < cnt.size(); i++) {
			int x = a % cnt[i];
			if (x == a) {
				ans = min(ans, tt + x - 1);
			} else {
				dfs1((a - x) / cnt[i], (b - x) / cnt[i], tt + x + 1);
			}
			dfs1(((cnt[i] - x) + a) / cnt[i], ((cnt[i] - x) + b) / cnt[i], tt + cnt[i] - x + 1);
		}
	};
	dfs1(a, b, 0);
	cout << ans << endl;
	return;
}




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