#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int>pii;
typedef pair<long, long>pll;
int n, x, y;
int minn = 0x3ffff;

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;
}
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);
	int gcdValue = gcd(a, b);
	int flag = 1;
	for (int i = 2; i <= gcdValue; ++i) {
		if (gcdValue % i == 0 && isPrime(i) && flag == 1)
		{
			dfs(a / i, b / i, step + 1);
			flag = 0;
		}

	}
	dfs(a + 1, b + 1, step + 1);
}

void solve()
{
	int a, b;
	int step = 0;
	cin >> a >> b;
	if ( a == 1 || b == 1)
	{
		cout << 0 << endl;
		 return;
	}
	else if (a == b)
	{
		cout << a - 1 << endl;
		return;
	}
	minn = 0x3ffff;
	dfs(a, b, step);
	cout << minn << endl;


}

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