#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pii pair<int,int>
#define vec vector
#define vi vec<int>
#define vb vec<bool>
#define vs vec<string>
#define vc vec<char>
#define vvi vec<vec<int>>
#define vsi vec<basic_string<int>>
#define si basic_string<int>
#define asc(vv)  sort(vv.begin(),vv.end());
#define desc(vv)  sort(vv.rbegin(),vv.rend());
#define eu(vv) vv.erase(unique(vv.begin(),vv.end()),vv.end());
#define gg(nn) vec<basic_string<int>>g(nn+1,basic_string<int>());
#define pq priority_queue
#define cn int n;cin>>n;
#define cs string s;cin>>s;
#define cm int m;cin>>m;
#define ck int k;cin>>k;
#define cq int q;cin>>q;
#define cnm int n,m;cin>>n>>m;
#define cuv int u,v;cin>>u>>v;
#define cnk int n,k;cin>>n>>k;
#define cnmk int n,m,k;cin>>n>>m>>k;
#define A0 vec<int>a(n);for(int &i:a)cin>>i;
#define A1 vec<int>a(n+1);for(int i=1;i<=n;i++)cin>>a[i];
const int N = 2e5;
const int mod =1e9+7;
//const int mod =  998244353;
void solve(){
    map<pair<int,int>,int>h;
    queue<pair<int,int>>q;
    pair<int,int>f;
    cin>>f.first>>f.second;
    h[f]=0;
    q.push(f);
    while (!q.empty())
    {
        auto &cur=q.front();
        q.pop();
        int pw=h[cur];
        int g=__gcd(cur.first,cur.second);
        cur.first-=g;
        if(!h.count(cur)){
            if(cur.first==0&&cur.second==0){
                cout<<pw+1ll<<"\n";
                return;
            }
            h[cur]=pw+1ll;
            q.push(cur);
        }
        cur.first+=g;
        cur.second-=g;
        if(!h.count(cur)){
            if(cur.first==0&&cur.second==0){
                cout<<pw+1ll<<"\n";
                return;
            }
            h[cur]=pw+1ll;
            q.push(cur);
        }    
    }
    
}
/*
 
 */
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    //freopen("D:\\Dev\\CLionProject\\untitled\\w.txt", "w", stdout);
    int _=1;
    cin>>_;
    for(int i=1;i<=_;i++){
        solve();
    }
    return 0;
}