#include<bits/stdc++.h>
#define int long long
using namespace std;
int Read(){
	int x=0;
	char ch=getchar();bool f=0;
	while(ch<'0'||ch>'9') if(ch=='-')f=1,ch=getchar(); else if(ch==EOF)return 0; else ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen("1.in","w",stdout);
	int T=Read();
	while(T--){
		int a=Read(),b=Read();
		int g1=__gcd(a,b);
		a/=g1,b/=g1;
		int ans=30;
		int mx=__lg(a)*2+1;
		for(int i=0;i<(1<<mx);i++){
			int x=a,y=b;
			for(int j=0;j<=mx;j++){
				if(j+2>=ans)break;
//				cout<<x<<' '<<y<<endl;
				int g=__gcd(x,y);
				if(i&(1<<j)) x-=g;
				else y-=g;
				if(x==0||y==0){
					ans=min(ans,j+2);
					break;
				}
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}