#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define fo(i,a,b) for(ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,a,b) for(ll (i)=(a);(i)>=(b);(i)--)

using namespace std;
const int N=2e5+10;
int a,b;
map<pair<int,int>,int> mp;
int c[N];
int cnt=0;


//ll gcd(ll a, ll b) {
//  if (b == 0) return a;
//  return gcd(b, a % b);
//}
//
//ll bmul(ll a, ll b, ll m) {  // 快速乘
//  ull c = (ull)a * (ull)b - (ull)((long double)a / m * b + 0.5L) * (ull)m;
//  if (c < (ull)m) return c;
//  return c + m;
//}
//
//ll qpow(ll x, ll p, ll mod) {  // 快速幂
//  ll ans = 1;
//  while (p) {
//    if (p & 1) ans = bmul(ans, x, mod);
//    x = bmul(x, x, mod);
//    p >>= 1;
//  }
//  return ans;
//}
//
//bool Miller_Rabin(ll p) {  // 判断素数
//  if (p < 2) return 0;
//  if (p == 2) return 1;
//  if (p == 3) return 1;
//  ll d = p - 1, r = 0;
//  while (!(d & 1)) ++r, d >>= 1;  // 将d处理为奇数
//  for (ll k = 0; k < 10; ++k) {
//    ll a = rand() % (p - 2) + 2;
//    ll x = qpow(a, d, p);
//    if (x == 1 || x == p - 1) continue;
//    for (int i = 0; i < r - 1; ++i) {
//      x = bmul(x, x, p);
//      if (x == p - 1) break;
//    }
//    if (x != p - 1) return 0;
//  }
//  return 1;
//}
//
//ll Pollard_Rho(ll x) {
//  ll s = 0, t = 0;
//  ll c = (ll)rand() % (x - 1) + 1;
//  int step = 0, goal = 1;
//  ll val = 1;
//  for (goal = 1;; goal *= 2, s = t, val = 1) {  // 倍增优化
//    for (step = 1; step <= goal; ++step) {
//      t = (bmul(t, t, x) + c) % x;
//      val = bmul(val, abs(t - s), x);
//      if ((step % 127) == 0) {
//        ll d = gcd(val, x);
//        if (d > 1) return d;
//      }
//    }
//    ll d = gcd(val, x);
//    if (d > 1) return d;
//  }
//}
//
//void fac(ll x) {
//  if (x <= max_factor || x < 2) return;
//  if (Miller_Rabin(x)) {              // 如果x为质数
//    max_factor = max(max_factor, x);  // 更新答案
//    return;
//  }
//  ll p = x;
//  while (p >= x) p = Pollard_Rho(x);  // 使用该算法
//  while ((x % p) == 0) x /= p;
//  fac(x), fac(p);  // 继续向下分解x和p
//}



int find(int a,int b)
{
	int fa;
	if(a<=0)return 1e9+10;
	if(a==1)return 0;
	if(b==1)return a-1;
	if(mp.find(make_pair(a,b))!=mp.end()) return mp[make_pair(a,b)];
	int ans=a-1;
	for(int i=0;i<cnt;i++)
	{
		if(c[i]>b)break; 
		if(b%c[i])continue;

		fa=c[i];
		ans=min(ans,1+a%fa+find(a/fa,b/fa));
		ans=min(ans,1+(fa-a%fa)+find(a/fa+1,b/fa));
	}	
	mp[make_pair(a,b)]=ans;
//	cout<<a<<" "<<b<<" "<<ans<<"\n";
	return ans;
}


void solve()
{
	cin>>a>>b;
	
	if(a>b)swap(a,b);
	b=b-a;
	int x=b;
	cnt=0;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0) {
			c[++cnt]=i;
			while (x%i==0) x/=i;
		}
	}
	if(x>1)
	{
		c[cnt]=x;
		cnt++;
	}
//	for(int i=0;i<cnt;i++)
//	{
//		cout<<c[i]<<" ";
//	}
	cout<<find(a,b)<<"\n";
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
//	init();
//	for(int i=0;i<cnt;i++)
//	{
//		cout<<pr[i]*pr[i]<<" ";
//	}
//	cout<<"\n";
	int T=1;
	cin>>T;
	while(T--) solve();
	return 0;
}