#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
#define PII pair<int,int>
#define int long long
constexpr int mod = 998244353, N = 2e5 + 5, M = 2e5 + 5;

void solve(){
    int a,b;
    cin>>a>>b;
    int ans=26;
    function<void (int res,int a,int b)> dfs=[&](int res,int a,int b){
        if(a==b and b==0){
            ans=min(ans,res);
            return ;
        }
        if(res>=ans)return;
        int d=gcd(a,b);
        dfs(res+1,a-d,b);
        dfs(res+1,a,b-d);
    };
    dfs(0,a,b);
    cout<<ans<<endl;


}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();

    return 0;
}