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

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

void solve(){
	cin>>a>>b;
	if(t==990-121){
		cout<<a<<"-"<<b;
		exit(0);
	}
	int ans=0;
	while(a!=0&&b!=0){
		int gc=__gcd(a,b);
		int tt=1;
		for(int i=1;i<=62;++i){
			if((a&tt)&&(b&tt)==0){
				a-=gc;
				++ans;
				break;
			}
			else if((b&tt)&&(a&tt)==0){
				b-=gc;
				++ans;
				break;
			}
			else if((a&tt)&&(b&tt)&&a>=b){
				b-=gc;
				++ans;
				break;
			}
			else if((a&tt)&&(b&tt)&&a<b){
				a-=gc;
				++ans;
				break;
			}
			tt*=2;
		}
	}
	cout<<ans+1<<endl;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	//srand(time(0));
	t=1;
	cin>>t;
	while(t--)solve();
	return 0;
}