#include<bits/stdc++.h>
using namespace std;
int T,a,ans,t;
long long b;
int bgcd(int a,int b){
	int at=__builtin_ctz(a),bt=__builtin_ctz(b),t=min(at,bt);
	b>>=bt;
	while(a){
		a>>=at;
		int c=a-b;
		b=min(a,b),a=abs(c),at=__builtin_ctz(a);
	}
	return b<<t;
}
void dfs(int a,int b,int cnt){
	if(cnt>=ans)
		return ;
	if(a==0||b==0){
		ans=min(ans,cnt+1);
		return ;
	}
	int g=bgcd(a,b);
	dfs(a,b-g,cnt+1);
	dfs(a-g,b,cnt+1);
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%lld",&a,&b),t=0;
		for(int i=0;i<=20;i++)
			if(a>=(1<<i))
				t+=2;
		ans=t,dfs(a,b,0);
		printf("%d\n",ans);
	}
	return 0;
}