#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
#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=1e4+11;
int cas,A,B,d,sta[MAXN];
pii g[MAXN]; bool vis[MAXN];
bool is(int x){
    for(int i=2;i*i<=x;i++) if(x%i==0) return 0;
    return 1;
}
int main(){
    //freopen("1.in","r",stdin);
    cas=read(); while(cas--){
        A=read(),B=read(); if(A>B) swap(A,B);
        if(A==1){printf("0\n"); continue;}
        if(A==B){printf("1\n"); continue;}
        d=B-A;  sta[0]=0;
        for(int i=1;i*i<=d;i++) if(d%i==0){
            sta[++sta[0]]=i;
            if(d!=i*i) sta[++sta[0]]=d/i;
        } sort(sta+1,sta+sta[0]+1); for(int i=1;i<=sta[0];i++) vis[i]=0,g[i]=mp(INT_MAX,INT_MAX);
        g[sta[0]]=mp(0,A);
        while(1){
            int Minn=INT_MAX,pos=-1;
            for(int i=1;i<=sta[0];i++) if(g[i].fi<Minn&&vis[i]==0) Minn=g[i].fi,pos=i;
            if(pos==-1) break;

            //cerr<<"d:"<<sta[pos]<<" w:"<<g[pos].fi<<" best_pos:"<<g[pos].se<<endl;
            vis[pos]=1;
            for(int i=1;i<pos;i++) if(sta[pos]%sta[i]==0){
                if(is(sta[pos]/sta[i])==0) continue;
                int p=g[pos].se,ww=(sta[pos]/sta[i]),flo=p/ww;
                if(p-flo*ww<=(flo+1)*ww-p){
                    g[i]=min(g[i],mp(g[pos].fi+p-flo*ww+1,flo));
                }else{
                    g[i]=min(g[i],mp(g[pos].fi+(flo+1)*ww-p+1,flo+1));
                }
            }
        }
        int Minn=INT_MAX;
        for(int i=1;i<=sta[0];i++) Minn=min(Minn,g[i].fi+g[i].se-1);
        printf("%d\n",Minn);
        
    }
}

answer.code: In function ‘int main()’:
answer.code:40:81: error: ‘INT_MAX’ was not declared in this scope
   40 |         } sort(sta+1,sta+sta[0]+1); for(int i=1;i<=sta[0];i++) vis[i]=0,g[i]=mp(INT_MAX,INT_MAX);
      |                                                                                 ^~~~~~~
answer.code:10:1: note: ‘INT_MAX’ is defined in header ‘<climits>’; did you forget to ‘#include <climits>’?
    9 | #include<ctime>
  +++ |+#include <climits>
   10 | #define pii pair<int,int>
answer.code:43:22: error: ‘INT_MAX’ was not declared in this scope
   43 |             int Minn=INT_MAX,pos=-1;
      |                      ^~~~~~~
answer.code:43:22: note: ‘INT_MAX’ is defined in header ‘<climits>’; did you forget to ‘#include <climits>’?
answer.code:44:81: error: ‘pos’ was not declared in this scope; did you mean ‘pow’?
   44 |             for(int i=1;i<=sta[0];i++) if(g[i].fi<Minn&&vis[i]==0) Minn=g[i].fi,pos=i;
      |                                                                                 ^~~
      |                                                                                 pow
answer.code:45:16: error: ‘pos’ was not declared in this scope; did you mean ‘pow’?
   45 |             if(pos==-1) break;
      |                ^~~
      |                pow
answer.code:48:17: error: ‘pos’ was not declared in this scope; did you mean ‘pow’?
   48 |             vis[pos]=1;
      |                 ^~~
      |                 pow
answer.code:52:22: error: ‘flo’ was not declared in this scope
   52 |                 if(p-flo*ww<=(flo+1)*ww-p){
      |                      ^~~
answer.code:52:26: error: ‘ww’ was not declared in this scope
   52 |                 if(p-flo*ww<=(flo+1)*ww-p){
      |                          ^~
answer.code:59:18: error: ‘INT_MAX’ was not declared in this scope
   59 |         int Minn=INT_MAX;
      |                  ^~~~~~~
answer.code:59:18: note: ‘INT_MAX’ is defined in header ‘<climits>’; did you forget to ‘#include <climits>’?