#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);
    }
    if(dp > upper) return;
    ll g = __gcd(a,b);
    dfs(a-g,b,dp+1);
    dfs(a,b - g,dp+1);
}

void solve(){
    ll a,b;cin>>a>>b;
    upper = log2(a) + 1;
    upper = upper * 2 + 2;
    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();
}