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

int dp[5050];
int mi;
set<pair<int,int>>s;
void dfs(int x,int y,int c){
  
  int g=__gcd(x,y);
  x/=g,y/=g;
  if(s.count({x,y}))return;
  s.insert({x,y});
  if(c+2>=mi)return;
  if(y%x==0){
    mi=min(mi,c+2);
    return;
  }
  
//  cout<<x<<" "<<y<<'\n';
  if(y%2==0){
    dfs(x-1,y,c+1);
    dfs(x,y-1,c+1);
    dfs(x-1,y-1,c+2);
    return;
  }
  if(x%2==0){
    
    dfs(x,y-1,c+1);
    dfs(x-1,y,c+1);
    dfs(x-1,y-1,c+2);
    return;
  }
  
  dfs(x-1,y-1,c+2);
  dfs(x-1,y,c+1);
  dfs(x,y-1,c+1);
}
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;
        s.clear();
        memset(dp,0x3f,sizeof(dp));
        int g=__gcd(x,y);
        x/=g,y/=g;
        mi=1e9;
        dfs(x,y,0);
        cout<<mi<<'\n';
        

       
        
    }

    
    

}

/*

5 8
6 11

7 24
6 24

9 82
8 51
6 50
5 9

8 93
7 91

24 255
*/