#include<bits/stdc++.h>

#define int long long

int sol(int a,int b){
    // std::cerr << a << ' ' << b << '\n';  
    if(a==0 && b==0)return 0;
    if(a==0||b==0)return 1;
    int g = std::gcd(a,b);
    int k1 = a / g, k2 = b / g; 

    int res = k2-k1+2;


    if(k1==1){
        res = std::min(res, sol(0,b)+1);
    }
    if(k1%2){
        res = std::min(res,sol(a-g,b)+1);
    }


    return sol(a,b-g)+1;

}

void solve(){
    int a,b;
    std::cin >> a >> b; 

    std::cout<<sol(a,b)<<"\n";


}
 
signed main(){
    
    int t = 1;
    std::cin >> t;
    while(t--)solve();

    return 0;
}