#include <bits/stdc++.h>


using namespace std;


#define lll __int128_t
#define ll __int128_t
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


ostream &operator<<(ostream &out, __int128_t a){
    out << (long long)a;
    return out;
}


istream &operator>>(istream &in, __int128_t &a){
    long long x;
    in >> x;
    a = x;
    return in;
}


mt19937 rnd(234);
const lll inf = 3e18;


ll gcd(ll a, ll b){
    while(a != 0){
        b %= a;
        swap(a, b);
    }
    return b;
}


struct bebra{
    lll x, y;

    bebra(){}
    bebra(lll x, lll y) : x(x), y(y) {}

    bebra inv(){
        return bebra(y, x);
    }
};


bool operator<(const bebra &a, const bebra &b){
    return a.x * b.y < a.y * b.x;
}

bool operator<=(const bebra &a, const bebra &b){
    return a.x * b.y <= a.y * b.x;
}



bebra operator+(const bebra &a, const bebra &b){
    return bebra(a.x + b.x, a.y + b.y);
}


bebra operator-(const bebra &a, const bebra &b){
    return bebra(a.x - b.x, a.y - b.y);
}


bebra operator*(const bebra &a, ll f){
    return bebra(a.x * f, a.y * f);
}


bebra min(const bebra &a, const bebra &b){
    if(a < b){
        return a;
    }
    return b;
}


bebra max(const bebra &a, const bebra &b){
    if(a < b){
        return b;
    }
    return a;
}


ll solve_slow(ll a, ll b){
    ll rs = 0;

    bebra l(0, 1);
    bebra r(inf, 1);
    bebra opt(a, b);
    bebra t(0, 0);
    while(t.x < opt.x || t.y < opt.y){
        if(t <= opt){
            l = max(l, t);
            t.x += 1;
        } else{
            r = min(r, t);
            t.y += 1;
        }
        if(l <= t && t < r){
            rs += 1;
        }
    }
    return rs;
}



bebra get_opt(bebra t){
    if(t.x == 1){
        return bebra(0, 1);
    }
    if(t.x < t.y){
        ll f = t.y / t.x;
        t.y -= t.x * f;
        auto opt = get_opt(t);
        opt.y += opt.x * f;
        return opt;
    } else{
        ll f = t.x / t.y;
        if(t.y * f == t.x){
            f -= 1;
        }
        t.x -= t.y * f;
        auto opt = get_opt(t);
        opt.x += opt.y * f;
        return opt;
    }
}


ll solve_high(ll a, ll b){
    ll rs = 0;
    while(a != 1){
        if(b == 1){
            rs += a - 1;
            break;
        }
        auto [na, nb] = get_opt(bebra(a, b));
        ll g = gcd(na, nb);
        na /= g;
        nb /= g;
        ll t = ((a - 1) / na);
        rs += t;
        a = na;
        b = nb;
    }
    return rs;
}


ll solve_low(ll a, ll b){
    ll rs = 0;
    while(b != 1){
        if(a == 1){
            rs += b - 1;
            break;
        }
        auto [nb, na] = get_opt(bebra(b, a));
        ll g = gcd(na, nb);
        na /= g;
        nb /= g;
        rs += 1;
        a = na;
        b = nb;
    }
    return rs;
}


ll solve(ll a, ll b){
    ll rs = 0;
    ll g = gcd(a, b);
    rs += (g - 1) * 2;
    a /= g;
    b /= g;
    if(a == b){
        rs += 1;
        return rs;
    }
    rs += 1;
    rs += solve_high(a, b);
    rs += solve_low(a, b);
    return rs;
}




void stress(){
    ll mxc = 10;
    ll c = 0;
    while(1){
        cout << ++c << "\n";
        ll a = rnd() % mxc + 1;
        ll b = rnd() % mxc + 1;
        ll right_rs = solve_slow(a, b);
        ll my_rs = solve(a, b);
        if(right_rs != my_rs){
            cout << a << " " << b << "\n";
            break;
        }
    }
}


int32_t main(){
    // stress();
    if(0){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    if(0){
        for(int i = 1; i <= 20; i += 1){
            for(int j = 1; j <= 20; j += 1){
                cout << std::setfill('0') << std::setw(2) << solve_slow(i, j) << " ";
            }
            cout << "\n";
        }
    }
    int t;
    cin >> t;
    while(t--){
        ll a, b;
        cin >> a >> b;
        // assert(a <= 1e6 && b <= 1e6);
        cout << solve(a, b) << "\n";
    }
    return 0;
}

/*
6
1 1
3 5
4 7
8 20
4 10
27 21

1
1 10000000000000

*/