#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);
#define int ll
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;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
vi plst,flst; 
void pgen(int x){
  int a=sqrt(x)+10;
  forw(i,2,a){
    int cnt=0;
    while(x%i==0)x/=i,++cnt;
    if(cnt)plst.push_back(i);
  }if(x!=1)plst.push_back(x);
}
void fgen(int x){
  if(x==1){flst={1};RN;}
  int p=0;
  for(auto q:plst)if(x%q==0)p=q;
  int cnt=0;
  while(x%p==0)++cnt,x/=p;
  fgen(x);
  int bas=flst.size(),siz=bas,mult=p;
  flst.resize(siz*(cnt+1));
  forw(i,0,cnt){
    forw(j,0,siz)flst[j+bas]=flst[j]*mult;
    bas+=siz,mult*=p;
  }
}
int ans;
unordered_map<ll,int> st;
int dfag(int x,int m,int d){
  if(d>=ans)RN INF;
  int idx=1LL*x*INF+m,ret=INF;
  auto pt=st.find(idx);
  if(pt!=st.end()){
    ret=pt->second+d;
    ans=min(ans,ret);
    RN ret;
  }
  int& lk=st[idx];
  if(m==1) ret=x+d;
  else{
    int k=x/m,r=x%m;
    for(auto p:plst)if(m%p==0){
      ret=min(ret,dfag(r,m/p,d+k+1));
      if(r)ret=min(ret,dfag(m-r,m/p,d+k+2));
  }}
  lk=ret-d;
  ans=min(ans,ret);
  RN ret;
}
void clear(){
  ans=INF;
  plst.clear(),flst.clear();
}
void solve(){
  int a,b; read(a,b);
  int x=a-b; x=x<0?-x:x;
  pgen(x); fgen(x);
  // for(auto f:flst)cout<<f<<' ';
  // cout<<endl;
  for(auto y1:{a,b})for(auto y2:flst)
    dfag(y1,y2,0);
  cout<<ans-1<<'\n';
}
void test(){
  pgen(120); fgen(120);
  for(auto f:flst)cout<<f<<' ';
  cout<<endl;
}
signed main()
{
  // test();
  int t;read(t);
  while(t--){
    clear();
    solve();
  }
  RN 0;
}
/*
1
2 1
*/
/*
10
651 806
667 787
243 758
932 572
311 420
596 805
40 581
349 396
496 843
399 751
*/