#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

inline int gcd(int x,int y)
{
	if(!x) return y;
	if(!y) return x;
	int t=__builtin_ctzll(x|y);
	x>>=__builtin_ctzll(x);
	do
	{
		y>>=__builtin_ctzll(y);
		if(x>y) swap(x,y);
		y-=x;
	}while(y);
	return x<<t;
}

struct node
{
	int a,b;
	int much;
};

int ans;

void solve()
{
	ans=1e15;
	queue<node>q;
	node term;
	cin>>term.a>>term.b;
	term.much=0;
	q.push(term);
	while(!q.empty())
	{
		node ttt=q.front();
		q.pop();
		if(ttt.much>=27) continue;
		int now_a=ttt.a;
		int now_b=ttt.b;
		int now_much=ttt.much;
		if(now_a==0&&now_b==0)
		{
			ans=min(ans,now_much);
			continue;
		}
		int g=gcd(now_a,now_b);
		if(now_a>0) q.push({now_a-g,now_b,now_much+1});
		if(now_b>0) q.push({now_a,now_b-g,now_much+1});
	}
	cout<<ans<<endl;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int t=1;
	cin>>t;
	while(t--)
	{
		solve();
	}
	
	
	
	
	
	return 0;
 }