#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) {}
};


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;
}



ll solve_high(bebra opt, bebra da, bebra db, ll da_cnt, ll db_cnt){
    if(da_cnt == 0 || db_cnt == 0){
        return da_cnt + db_cnt;
    }
    ll tr = da_cnt;
    ll tl = -1;
    while(tl + 1 < tr){
        ll tm = (tl + tr) / 2;
        if(da * tm + db <= opt){
            tr = tm;
        } else{
            tl = tm;
        }
    }
    ll t = tr;
    ll new_da_cnt = db_cnt * t - da_cnt;
    ll new_db_cnt = da_cnt - db_cnt * (t - 1);
    bebra new_da = da * (t - 1) + db;
    bebra new_db = da * (t - 1) + db;
    ll rs = t;
    rs += solve_high(opt, new_da, new_db, new_da_cnt, new_db_cnt);
    return rs;
}


ll solve_high(ll a, ll b){
    ll rs = 0;
    ll tr = b;
    ll tl = -1;
    while(tl + 1 < tr){
        ll tm = (tl + tr) / 2;
        if(a * tm < b){
            tl = tm;
        } else{
            tr = tm;
        }
    }
    ll t = tr;
    bebra da(1, t);
    bebra db(1, t - 1);
    bebra opt(a, b);
    ll da_cnt = b - a * (t - 1);
    ll db_cnt = a * t - b;
    rs += solve_high(opt, da, db, da_cnt, db_cnt);
    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 += solve_slow(a, b);
    return rs;
    rs += solve_high(a, b);
    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(opt < t && t < r){
            rs += 1;
        }
    }
    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;
}

/*
1
3 5


1
1 10000000000000

*/