#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef pair<int,int> PII;
#define endl '\n'
#define debug(x) cout<<#x<<": "<<x<<endl
const int N=1e5+10;
#define lowbit(x) (x&-x)

map<PII,int>dp;

vector<int> get_prime_divisors(int x)
{
	vector<int> res;
	for(int i=2;i*i<=x;i++)
	{
		while(x%i==0)
		{
			res.push_back(i);
			x/=i;
		}
	}
	if(x!=1) res.push_back(x);
	return res;
}

vector<int> get_divisors(int x)
{
	vector<int> res;
	for(int i=1;i*i<=x;i++)
	{
		if(x%i==0)
		{
			if(i!=1) res.push_back(i);
			if(i!=x/i) res.push_back(x/i);
		}
	}
	return res;
}

int dfs(int a,int c)
{
	if(a==1) return 0;
	if(c==1) return a-1;
	if(dp.count({a,c})) return dp[{a,c}];
	vector<int>path=get_prime_divisors(c);
	int ans=1e9;
	for(auto g:path)
	{
		int ans1=1e9;
		if(a>=g) ans1=dfs((a-a%g)/g,c/g)+a%g+1;
		int ans2=dfs((a+g-a%g)/g,c/g)+g-a%g+1;
		ans=min({ans,ans1,ans2});
		
	}
	return dp[{a,c}]=ans;
}

void solve()
{
	int a,b;
	cin>>a>>b;
	if(a>b) swap(a,b);
	cout<<dfs(a,b-a)<<endl;
}	

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	int T=1;
	cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}