#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
int a[1110110],b[1101010],c[1100110],d[202020];
string s[1010100];
vector<int>g[202020];
pair<int,int>p[202020];

double pi=acos(-1);
double f(pair<int,int>a){
  if(a.second==0){
    if(a.first>0){
      return 0;
    }
    return pi;
  }
  double d=sqrt((double)a.second*a.second+a.first*a.first);
  double th=acos((double)1.0*a.first/d);
  if(a.second>0){
    return th;
  }
  return 2*pi-th;
}
bool cmp(pair<int,int>a,pair<int,int>b){
  return f(a)<f(b);
}
signed main(){
  //  ios::sync_with_stdio(false);cin.tie(0);
//    cout<<acos(1)<<" "<<acos(-1)<<'\n';
    int _=1;
    cin>>_;
    pi=3.1415926535897932384626;
    // printf("%.18Lf\n",pi);
    int i,j;
    int n;
    while(_--){
        int n,m,l,k,w;
        int x,y;
        cin>>x>>y;
        int c=0;
        if(x>y)swap(x,y);
        while(x){
          while(__gcd(x,y-__gcd(x,y))>__gcd(x,y)){
            y-=__gcd(x,y);
            c++;
          }
          x-=__gcd(x,y);
          c++;
        }
        c++;
        cout<<c<<'\n';
        

       
        
    }

    
    

}

/*

18
8 22 

8 20

*/