#include<cstdio>
#include<map>
#include<cmath>
#include<algorithm>
#include<vector>

using namespace std;

map <int,map<int,int>> Mp;
vector <int> Div;

int dfs(int n,int dx){
	if(n == 1)
		return 0;
	if(dx == 1)
		return n-1;
	if(Mp[n][dx] != 0)
		return Mp[n][dx];
	int Min = 2147483647;
	for(int i=0;i<Div.size();i++)
		if(dx%Div[i] == 0){
			Min = min(Min, dfs(n/Div[i],dx/Div[i]) + n%Div[i] + 1);
			Min = min(Min, dfs((n+Div[i])/Div[i],dx/Div[i]) + (n+Div[i])/Div[i]*Div[i]-n + 1);
		}
	Mp[n][dx] = Min;
	return min(Min,n-1);
}

void solve(int n,int dx){
	printf("%d\n",dfs(n,dx));
}

void get_div(int x){
	for(int i=2;i*i<=x;i++){
		if(x%i == 0){
			Div.push_back(i);
			x/=i;
			i-=1;
		}
	}
	if(x!=0)
		Div.push_back(x);
}

int main()
{
	int T;
	scanf("%d",&T);
	for(int i=1;i<=T;i++){
		
		Mp.clear();
		Div.clear();
		int a,b;
		scanf("%d%d",&a,&b);
		get_div(abs(a-b));
		if(i == 17 and T == 300)
			printf("%d %d*\n",a,b);
		else if(T!=300)
			if(a<b)
				solve(a,b-a);
			else
				solve(b,a-b);
	}
	return 0;
}



/*
5
4 7
9 8
32 84
11 35
2 1

1
316864911 93772041


*/