#include<bits/stdc++.h>

using namespace std;

#define endl "\n"
#define ll long long

ll upper;
ll ans = 0;
void dfs(ll a,ll b,ll dp){
    if(a == 0 && b == 0){
        ans = min(ans , dp);
        return;
    }
    if(dp > upper || dp > ans || a < 0 || b < 0) return;
    ll g = __gcd(a,b);
    if(a/g%2==1){
        dfs(a-g,b,dp+1);
        dfs(a,b - g,dp+1);
    }else{
        dfs(a,b - g,dp+1);  
        dfs(a-g,b,dp+1);
    }
}

void solve(){
    ll a,b;cin>>a>>b;
    upper = log2(a);
    upper = upper * 2 + 1;
    ans = 1e9;
    dfs(a,b,0);
    cout<<ans<<endl;

}

int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    ll t;cin>>t;while(t--)
    solve();
}