#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;
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 dfa(int x,int m,int d){
  if(d>=ans)RN INF;
  int ret=INF;
  if(x==0 && m==1){
    ret=d;
  }else if(x<m){
    auto pt=st.find(x*INF*1LL+m);
    if(pt!=st.end())RN pt->second+d;
    auto& lk=st[x*INF+m];
    for(auto p:plst)if(m%p==0)
      ret=min(ret,dfa(x,m/p,d+1));
    lk=ret-d;
  }else{
    int k=x/m,r=x%m;
    ret=min(ret,dfa(r,m,d+k));
    if(r!=0)
      ret=min(ret,dfa(m-r,m,d+k+1));
  }
  // cout<<x<<' '<<m<<' '<<lk<<endl;
  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)
    dfa(y1,y2,0);
  cout<<ans-1<<'\n';
}
void test(){
  pgen(120); fgen(120);
  for(auto f:flst)cout<<f<<' ';
  cout<<endl;
}
int main()
{
  // test();
  int t;read(t);
  while(t--){
    clear();
    solve();
  }
  RN 0;
}
/*
1
2 1
*/