#include<bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
void solve(){
    int x,y;
    cin>>x>>y;
    int id=0;
    for(int i=20;i>=0;i--){
        if(x>>i&1){
            id=i+1;
            break;
        }
    }
    id*=2;
    int ans=1e18;
    for(int i=0;i<(1<<id);i++){
        int x1=x,y1=y;
        for(int j=0;j<id;j++){
            if(i>>j&1){
                y1-=gcd(x1,y1);
            }
            else x1-=gcd(x1,y1);
            if(x1==0&&y1==0){
                ans=min(ans,j+1);
                break;
            }
        }
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}