#include<bits/stdc++.h>
using namespace std;
typedef  long long LL;
typedef pair<LL,LL> PII;
const int N=2e5+10,M=2e6;
const int mod=998244353;
const LL P=1e9+7;
const LL INF=1e18;
LL h[N],e[M],ne[M],w[M],idx;
int T=1;

LL gcd(LL a,LL b){
    return b?gcd(b,a%b):a;
}

void solve(){
    LL a,b;
    cin>>a>>b;

    if(a>b) swap(a,b);

    LL t=b+a;

    //t%=a;

    LL res=0;
    while(t%a){
        res++;
        LL d=gcd(a,b);
        if(gcd(a-d,b)>gcd(a,b-d)) a-=d;
        else b-=d;

        t-=d;
        if(!a||!b) break;
    }

    //cout<<a<<" "<<b<<endl;
    if(a&&b) res+=2;
    else res++;

    cout<<res<<endl;
  
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //int T=1;
    cin>>T;

    while(T--) solve();
 
    return 0;
}