#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include <iomanip>

#define int long long
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
using namespace std;
typedef long long LL;
typedef __int128 i128;
typedef unsigned long long ULL;
typedef double db;

const int N = 1e5 + 10;
int a , b , cnt , p[N] , d , ans = 1e18;
map<pair<int , int> , bool>mp;
map<pair<int , int> , int>res;

int dfs(int a , int d){
	int now = a - 1;

	if(a == 0)return 1e18;
	if(a == 1)return 0;
	if(d == 1)return a - 1;

	if(res[{a , d}])return res[{a , d}];
	for(int i = 1 ; i <= cnt ; i ++){
		if(d % p[i] == 0){
			now = min({now , a % p[i] + 1 + dfs(a / p[i] , d / p[i]) , p[i] - a % p[i] + 1 + dfs(a / p[i] + 1 , d / p[i])});
		}
	}
	// mp[{a , d}] = true;
	return res[{a , d}] = now;
}

void Asuka()
{
	cin >> a >> b;
	if(a > b)swap(a , b);
	d = b - a;
	int x = d;
	for(int i = 2 ; i * i <= x ; i ++){
		if(x % i == 0){
			p[++ cnt] = i;
		}
		while(x % i == 0){
			x /= i;
		}
	}
	if(x != 1)p[++ cnt] = x;
	cout << dfs(a , d) << '\n';
	return;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t = 1;
	cin >> t;
	while(t --){
		Asuka();
	}
	return 0;
}