//in the name of allah
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
        ios_base::sync_with_stdio(false);cin.tie(NULL);
        int q;cin >> q;
        ll MX = 1e18;
        while(q--){
                ll a , b;cin >> a >> b;
                ll g = __gcd(a , b);
                a /= g;
                b /= g;
                ll ans=0;
                while(a && b){
                        if(a<b) swap(a , b);
                        ans += a/b;
                        a %= b;
                }
                cout << ans-1 << "\n";
        }
}