#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;
        if(cura==1||curb==1) {
            ans = min(ans,ds+2);
        } else {
            for(int i = 2;i<=min(cura,curb);i++) {
                if(!vis[i]){
                    if(ds+(cura%i)+(curb%i)<dis[i]) {

                        dis[i] = ds+(cura%i)+(curb%i);
                        q.emplace(dis[i],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();
    }
    
}