#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<numeric>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=5e3+10;
const int N=5e3;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
int n;
long long m,ans;
int g[MAXN][MAXN],lst[MAXN][MAXN];
#define swap(x,y) x^=y^=x^=y
inline int gcd(int a,long long b){
	if(a>b){
		swap(a,b);
	}
	if(!a){
		return b;
	}
	if(b%a==0){
		return a;
	}
	b%=a;
	if(a>b){
		swap(a,b);
	}
	return g[a][b];
}
inline void init(){
	for(int i=1;i<=N;i++)
	{
		g[i][i]=i;
		for(int j=i+1;j<=N;j++)
		{
			int k=j-i;
			g[i][j]=i<=k?g[i][k]:g[k][i];
		}
	}
	for(int i=1;i<=N;i++)
	{
		lst[i][0]=0;
		for(int j=1;j<i;j++)
		{
			if(g[j][i]>1){
				lst[i][j]=j;
			}
			else{
				lst[i][j]=lst[i][j-1];
			}
		}
	}
}
void dfs(int a,long long b,long long now){
	if(!a){
		ans=min(ans,now+1);
		return ;
	}
	if(b%a==0){
		ans=min(ans,now+2);
		return ;
	}
	if(b/a+now>ans){
		return ;
	}
	int cur=__gcd(0ll+a,b);
	int c=a/cur,d=b/cur%c;
	dfs(a,b-cur,now+1);
	dfs(a-cur,b,now+1);
}
inline void solve(){
	scanf("%d%lld",&n,&m);
	if(n>m){
		swap(n,m);
	}
	ans=LINF;
	dfs(n,m,0);
	printf("%lld\n",ans);
}
signed main(){
	#ifdef LOCAL
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	atexit([](){fprintf(stderr,"%.3lfs\n",(double)clock()/CLOCKS_PER_SEC);});
	#endif
	init();
	int t;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
	return 0;
}