#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
#define rep(i, a, b) for(int i = a; i <= b; i ++ )
#define pre(i, a, b) for(int i = a; i >= b; i -- )
const int N = 1e6 + 10;
int a, b, ans;
void dfs(int a, int b, int c)
{
    if(c > 30) return;
    if(!a && !b)
    {
        ans = min(ans, c);
        return;
    }
    if(a)
    dfs(a - __gcd(a, b), b, c + 1);
    if(b)
    dfs(a, b - __gcd(a, b), c + 1);
}
void solve()
{
    ans = 1e9;
    cin >> a >> b;
    dfs(a, b, 0);
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int _;
    cin >> _;
    while(_ -- )
    {
        solve();
    }
    return 0;
}