#include <bits/stdc++.h>
using namespace std;
#define RN return
#define forw(_,l,r) for(auto _=(l);_<(r);++_)
#define fors(_,r,l) for(auto _=(r);_>(l);--_)
#define fastio cin.tie(0),cout.tie(0),ios::sync_with_stdio(0);
void read(){}
template<typename T,typename...Types>
void read(T&a,Types&...args){
  a=0; char c=' ';
  while(isspace(c))c=getchar();
  while(isdigit(c))a=10*a+c-'0',c=getchar();
  read(args...);
}
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f,NUM=1e5;
const ll INFL=0x3f3f3f3f3f3f3f3f;
int lst[NUM][3]={},top=0,a,b;
void clear(){
  top=-1;
}
void dfs(int bg,vector<pii>& pv){
  // cout<<bg<<':';
  // for(auto [p,c]:pv)cout<<p<<' '<<c<<' ';
  // cout<<"---\n";
  vector<pii> pv2; int ltop=1;
  for(auto [p,c]:pv){
    int siz=ltop;
    memset(lst+siz,0x3f,((ltop*=(c+1))-siz)*sizeof(lst[0]));
    for(int i=0,base=bg;i<c;++i,base+=siz){
      for(int j=base,k=j+siz;j<base+siz;++j,++k){
        lst[k][2]=lst[j][2]*p;
        int f1=lst[k][2],f0=lst[j][2],x0=b%f0,x1=b%f1;
        int y0=x0?f0-x0:0,y1=x1?f1-x1:0;
        lst[k][0]=min(lst[k][0],lst[j][0]+1+x1/f0);
        lst[k][1]=min(lst[k][1],lst[j][1]+1+y1/f0);
        if(x1==y1)lst[k][1]=lst[k][0]=min(lst[k][1],lst[k][0]);
        else{
          lst[k][0]=min(lst[k][0],lst[j][1]+2+y1/f0);
          lst[k][1]=min(lst[k][1],lst[j][0]+2+x1/f0);
        }
      }dfs(base+siz,pv2);
    }pv2.push_back({p,c});
  }top=ltop;
}
void solve(){
  read(a,b);
  if(a<b)swap(a,b);
  int x=a-b; 
  forw(i,0,3)lst[0][i]=i/2;
  vector<pii> pv;
  int sq=sqrt(x)+10;
  forw(i,2,sq){int c=0;while(x%i==0)++c,x/=i;if(c)pv.push_back({i,c});}
  if(x!=1)pv.push_back({x,1});
  dfs(0,pv);
  int ans=INF;
  forw(i,0,top){
    int f=lst[i][2],del=b/f;
    ans=min({ans,lst[i][0]+del,lst[i][1]+del+1});
  }cout<<ans-1<<'\n';
}
signed main()
{
  // solve();
  // forw(i,0,ltop)cout<<lst[i][2]<<' ';
  // RN 0;
  // cout<<lst[ltop-1][2]<<endl;
  // test();
  int t;read(t);
  while(t--){
    clear();
    solve();
  }
  RN 0;
}
/*
1
615 433
223528529 446621399
*/
/*
10
651 806
667 787
243 758
932 572
311 420
596 805
40 581
349 396
496 843
399 751
*/