#include<bits/stdc++.h> 
using namespace std;
#define fer(i,a,b) for(int i=a;i<=b;i++)
#define fdr(i,a,b) for(int i=a;i>=b;i--)
#define int long long
#define xx first
#define yy second
#define pb push_back
#define ps push
#define db double
#define P pair<int,int>
#define endl '\n'
#define ll long long
const int N=2e5+10;
const int mod=1e9+7;
const int INF=1e18+10;
priority_queue<int,vector<int>,greater<int>> pq;

int n;
vector<int> v;
map<P,int> mp;

void get(int x){
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			v.pb(i);
			while(x%i==0) x/=i;
		}
	} 
	if(x>1) v.pb(x);
}

int dfs(int a,int c){
	if(a==1) return 0;
	if(c==1) return a-1;
	if(mp[{a,c}]) return mp[{a,c}];
	int res=a-1;
	for(int d:v){
		if(c%d==0){
			int rest=a%d;
			int tmp1=rest+1+dfs(a/d,c/d);
			int tmp2=(d-rest)+1+dfs(a/d+1,c/d);
			res=min({res,tmp1,tmp2});
		}
	}
	return mp[{a,c}]=res;
}

void solve(){
	int a,b;
	cin>>a>>b;
	int c=abs(a-b);
	get(c);
	cout<<dfs(min(a,b),c)<<endl;
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	int tt;
	cin>>tt;
	while(tt--){
		solve(); 
	} 
}