#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++;
            }else if(k2%2 == 1){
                b -= gcd(a,b);
                k2--;
                cnt++;
            }
            else{
                k1 = a/gcd(a,b);
                k2 = b/gcd(a,b);
            }
            ans = min(k1+1+cnt,ans);
        }
        cout<<ans<<'\n';
    }
    return 0;
}