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

void solve(){
    i64 a,b;
    cin>>a>>b;
    assert(a <= 5000);
    int ans=26;
    function <void (int cur,int a,int b)> rec = [&]( int cur, i64 a, i64 b) -> void {
        if (a == 0 && b == 0) {
            ans = min(ans, cur);
            return;
        }
        if (cur >= ans) {
            return;
        }
        i64 g = gcd(a, b);
        if (a > 0) {
            rec( cur + 1, a - g, b);
        }
        if (b > 0) {
            rec( cur + 1, a, b - g);
        }
    };
    rec( 0, a, b);

    cout << ans << '\n';


}

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

    return 0;
}