#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll dis[5010];
int vis[5010];
const ll inf = 1e18;
void solve()
{
    //k1g,k2g
    //(k1-1)g,k2g.
    //gcd(k1-1,k2).
    //因此可以观察到,无论什么顺序操作,g都在递增.
    //考虑他们希望引入t来增强g.
    //那么两边减到t的倍数即可.
    //3 7 -> g = 2? ok.(2,1,3) 共6步
    //3 7 -> g = 3? ok.(3,1,2) 共4步
    //这很困难,甚至还有一个可达性的问题.
    //比如: 不一定所有t都是可到达的.
    //21、16 然后目标是2?
    //-> 20 16,t = 4.
    //-> 21,15 t = 3.做不到t = 2!
    //21,15 -> 7,5.
    //我们知道,走log(十几条边)以后,a就会呗榨干.但是那有什么用呢?
    
    //复杂度:O(∞)
    //例如:a = 100,b = 1e9+7.
    //你的所谓对齐,就是下取整除法嘛。
    //下取整的除法顺序是可以随意更换的
    //意味着,g唯一确定时,a、b都唯一确定了,就是a/g和b/g.
    //但是我们仍然不能处理可达性bug,不妨直接不考虑这个bug.
    ll a,b;
    cin>>a>>b;
    for(int i = 1;i<=a;i++) {dis[i] = inf;vis[i] = 0;}
    ll gg = __gcd(a,b);dis[gg] = 0;
    ll ans = inf;
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<>> q;
    q.emplace(0,gg);
    while(!q.empty()) {
        auto [ds,ggg] = q.top();q.pop();
        //cout<<ds<<" "<<ggg<<endl;
        if(vis[ggg]) continue;;
        vis[ggg] = 1;
        ll cura = a/ggg,curb = b/ggg;
        //ans = min(ans,ds+min(cura,curb)+1);
        //666这个入是桂。
        if(cura==1||curb==1) {
            ans = min(ans,ds+2);
        } else {
            queue<pair<ll,ll>> qq;
            set<pair<ll,ll>> vist;
            qq.emplace(cura,curb);
            set<int> okdi;
            while(!qq.empty()) {
                auto [sa,sb] = qq.front();qq.pop();//can be end
                if(sa==0||sb==0) {
                    ans = min(ans,ds+min(cura,curb)+1);
                } else {
                auto p1 = make_pair(sa-1,sb);
                auto p2 = make_pair(sa,sb-1);
                if(__gcd(sa-1,sb)>1) okdi.emplace(__gcd(sa-1,sb));
                else if(vist.find(p1)==vist.end()) {
                    vist.insert(p1);qq.emplace(p1);
                } 
                if(__gcd(sa,sb-1)>1) okdi.emplace(__gcd(sa,sb-1));
                else if(vist.find(p2)==vist.end()) {
                    vist.insert(p2);qq.emplace(p2);
                } 
                }
            }
            for(auto & d:okdi) {
                if(d==1) continue;
                ll newg = d*ggg;
                    if(!vis[newg]){
                    if(ds+(cura%d)+(curb%d)<dis[newg]) {

                        dis[newg] = ds+(cura%d)+(curb%d);
                        q.emplace(dis[newg],newg);
                    }
                }
            }
            }
            // for(int i = 2;i<=min(cura,curb);i++) {
            //     if(!vis[i*ggg]){
            //         if(ds+(cura%i)+(curb%i)<dis[i*ggg]) {

            //             dis[i*ggg] = ds+(cura%i)+(curb%i);
            //             q.emplace(dis[i*ggg],i*ggg);
            //         }
            //     }
            // }
        //}
    }
    cout<<ans<<'\n';
}   

int main(){
    //init();
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T = 1;
    cin>>T;
    while (T--)
    {
        solve();
    }
    
}