#include<iostream>
using namespace std;
using ll = long long;
long long gcd(long long a, long long b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        long long a, b;
        cin >> a >> b;
        ll cnt = 0;
        ll k1 = a / gcd(a, b);
        ll k2 = b / gcd(a, b);
        ll ans = 1e15;
        while (a != 0)
        {
            if (k1 % 2 == 1) {
                a -= gcd(a, b);
                k1--;
                cnt++;
                if (k1 == 0) {
                    ans = min((k2 != 0) + cnt, ans);
                }
            }
            else if (k2 % 2 == 1) {
                b -= gcd(a, b);
                k2--;
                cnt++;
                if (k2 == 0) {
                    ans = min((k1 != 0) + cnt, ans);
                }
            }
            else {
                k1 = a / gcd(a, b);
                k2 = b / gcd(a, b);
            }
            ans = min(k1 + 1 + cnt, ans);
        }
        cout << ans << '\n';
    }
    return 0;
}