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


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

//5156 6326


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