#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
typedef pair<int,int> PII;

int n,m,k;
vector<int> p;
map<int,int> mp;
//unordered_map<int,> mp;
bool tf[N];
vector<PII> ys;
int ans;


void dfs(int x,int y,int num){
//		cout<<x<<" "<<y<<" "<<num<<endl;
		ans=min(ans,num+min(x,y)-1);
	if(x==1||y==1){
		return;
	}
	int dist=y-x;
	
//	cout<<"--"<<x<<" "<<y<<endl;
	for(auto [u,v]:ys){
//		cout<<dist<<" "<<u<<endl;
		if(dist%u!=0) continue;
		int tt=x%u;
		int num1=x-tt,num2=y-tt;
		int gg=u;
		
		int res=num+tt+mp[gg];
//		cout<<num1<<" "<<num2<<" "<<res<<" "<<tt<<" "<<mp[gg]<<endl;
		if(res<ans){
			dfs(num1/gg,num2/gg,res);
		}
		tt=u-tt;
		num1=x+tt,num2=y+tt;
		gg=gcd(num1,num2);
		res=num+tt+mp[gg];
		if(res<ans){
			dfs(num1/gg,num2/gg,res);
		}
	}
}

void dfs1(int x,int sum,int cnt){
	
	if(x>=ys.size()){
		mp[sum]=cnt;
		return;
	}
	int res=1,cc=0;
	for(int i=0;i<=ys[x].second;i++,res*=ys[x].first){
		dfs1(x+1,sum*res,cnt+i);
	}
}

void __(){
	cin>>n>>m;
	ans=min(n,m)-1;
	if(n>m) swap(n,m);
	int cha=m-n;
	ys.clear();
	mp.clear();
	for(int i=0;p[i]<=(m-n)/p[i];i++){
		int cnt=0;
		while(cha%p[i]==0){
			cnt++;
			cha/=p[i];
		}
		if(cnt!=0)
			ys.push_back({p[i],cnt});
	}
	if(cha!=1){
		ys.push_back({cha,1});
	}
	dfs1(0,1,0);
	
	dfs(min(n,m),max(n,m),0);
//	printf("%lld\n",ans);
	cout<<ans<<"\n";
}

int main(){
	
//	ios::sync_with_stdio(0);
//	cin.tie(0);
	for(int i=2;i<=100000;i++){
		if(!tf[i]) p.push_back(i);
		for(int j=0;p[j]<=100000/i;j++){
			tf[i*p[j]]=1;
			if(i%p[j]==0) break;
		}
	}
	
	int _;
	cin>>_;
	while(_--){
		__();
	}
	
}