#include<bits/stdc++.h>

using namespace std;
const int N = 305;
typedef long long ll;
typedef double db;
typedef pair<int, int>pii;
typedef pair<long, long>pll;
int n, x, y;
int minn = 0x3ffff;
long long arr[N];
int nowx, nowy;

int check(int a, int b)
{
	if (a == 1 || b == 1) return 1;
	else return 0;
}
bool isPrime(int num) {
	if (num <= 1)
		return false;
	for (int i = 2; i * i <= num; ++i) {
		if (num % i == 0)
			return false;
	}
	return true;
}
int gcd(int a, int b) {
	while (b != 0) {
		int temp = a % b;
		a = b;
		b = temp;
	}
	return a;
}
vector<int> findPrimesGCD(int num1, int num2) {
	vector<int> factors;
	int gcdValue = gcd(num1, num2);
	for (int i = 2; i <= gcdValue; ++i) {
		if (gcdValue % i == 0 && isPrime(i))
			factors.push_back(i);
	}
	return factors;
}

void dfs(int a, int b, int step)
{
	if (check(a, b))
	{
		minn = min(minn, step);
		return;
	}
	if (step > minn)
	{
		return;
	}
	dfs(a - 1, b - 1, step + 1);
	dfs(a + 1, b + 1, step + 1);
	vector<int> commonFactors = findPrimesGCD(a, b);
	for (int factor : commonFactors) {
		dfs(a / factor, b / factor, step + 1);
	}


}

void solve()
{
	int a, b;
	int step = 0;
	cin >> a >> b;
	dfs(a, b, step);
	cout << minn << endl;


}

int main()
{
	int tcase;
	cin >> tcase;
	while (tcase--)
		solve();


}