#include<bits/stdc++.h>
#define ll long long
#define fo(i,a,b) for(ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,a,b) for(ll (i)=(a);(i)>=(b);(i)--)
using namespace std;
const int N=2e5+10;
int n,a,b;
map<pair<int,int>,int> mp;
int vis[N];
int pr[N];
int cnt=0;
void init()
{
	
	for(int i=2;i<N;i++)
	{
		if(vis[i])continue;
		pr[cnt]=i;
		cnt++;
		for(int j=1;j<N/i;j++)
		{
			vis[j*i]=1;
		}
	}
}

bool pri(int x)
{
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			return false;
		}
	}
	return true;
}

int find(int a,int b)
{
	if(a==1)return 0;
	if(b==1)return a-1;
	int ans=a-1;
	for(int i=0;i<cnt;i++)
	{
		if(b%pr[i]==0)
		{
			ans=min(ans,1+a%pr[i]+find(a/pr[i],b/pr[i]));
			ans=min(ans,1+(pr[i]-a%pr[i])%pr[i]+find(a/pr[i]+1,b/pr[i]));
		}
	}
	if(pri(b))
	{
		ans=min(ans,1+a%b+find(a/b,1));
		ans=min(ans,1+(b-a%b)%b+find(a/b+1,1));
	}
	mp[make_pair(a,b)]=ans;
	return ans;
}


void solve()
{
	cin>>a>>b;
	if(a>b)swap(a,b);
	b=b-a;
	cout<<find(a,b)<<"\n";
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	init();
//	for(int i=0;i<cnt;i++)
//	{
//		cout<<pr[i]<<" ";
//	}
//	cout<<"\n";
	int T=1;
	cin>>T;
	while(T--) solve();
	return 0;
}