#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
#include<climits>
#include<map>
#define pii pair<int,int>
#define pb push_back
#define LL long long
#define mp make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
    int f=1,ans=0; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=2e5+11;
int v[MAXN],pri[MAXN],Lim=2e5,N,A,B,d,cas,sta[MAXN];
void Init(){
    for(int i=2;i<=Lim;i++){
        if(!v[i]) v[i]=i,pri[++pri[0]]=i;
        for(int j=1;j<=pri[0]&&pri[j]<=Lim/i;j++){
            v[i*pri[j]]=pri[j];
            if(i%pri[j]==0) continue;
        }
    }return;
}
map<pii,int> Hash; int num,F[MAXN]; bool vis[MAXN]; pii Tp[MAXN];
void Ins(int uu,int dd,int w){
    if(Hash[mp(uu,dd)]==0) Hash[mp(uu,dd)] = ++num,Tp[num]=mp(uu,dd),F[num]=INT_MAX;
    int id=Hash[mp(uu,dd)];
    F[id]=min(F[id],w); return;
}
int main(){
    //freopen("1.in","r",stdin);
    Init(); cas=read();
    while(cas--){
        A=read(),B=read(); if(A>B) swap(A,B); d=B-A; int cd=d; int tot=0; num=0;
        while(d!=1){
            int prime=v[d]; sta[++tot]=prime;
            while(d%prime==0) d/=prime;
        }
        Hash.clear();  Ins(A,cd,0);
        while(1){
            int Minn=INT_MAX,id=-1;
            for(int i=1;i<=num;i++) if(!vis[i]&&F[i]<Minn){Minn=F[i],id=i;}
            vis[id]=1;
            if(id==-1) break;
            int U=Tp[id].fi,D=Tp[id].se,W=F[id];
            //cerr<<"U:"<<U<<" D:"<<D<<" W:"<<W<<" "<<sta[1]<<endl;
            for(int i=1;i<=tot;i++) if(D%sta[i]==0){
                //cerr<<"i:"<<i<<endl;
                Ins(U/sta[i],D/sta[i],U-(U/sta[i])*sta[i]+1+W);
                Ins(U/sta[i]+1,D/sta[i],(U/sta[i]+1)*sta[i]-U+1+W);
            }
        }
        int Minn=INT_MAX;
        for(int i=1;i<=num;i++) Minn=min(Minn,F[i]+Tp[i].fi-1);
        printf("%d\n",Minn);
        for(int i=1;i<=num;i++) vis[i]=0;
        //return 0;
    }
}