#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#include<functional>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include<bits/stdc++.h>
#include <unordered_map>
#define ll            long long 
#define lowbit(x) (x & -x)
#define endl "\n"//                           交互题记得删除
using namespace std;
//using namespace __gnu_pbds;
mt19937 rnd(time(0));
const ll p = 998244353;
const ll mod = 998244353;
ll ksm(ll x, ll y)
{
	ll ans = 1;
	while (y)
	{
		if (y & 1)
		{
			ans = ans % mod * (x % mod) % mod;
		}
		x = x % mod * (x % mod) % mod;
		y >>= 1;
	}
	return ans % mod % mod;
}
ll gcd(ll x, ll y)
{
	if (y == 0)
		return x;

	else
		return gcd(y, x % y);
}
void fio()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
struct s
{
	ll l, r;
	bool operator<(const s& a)const
	{
		return l < a.l;
	}
};
ll dp[5004][5004][2];
int main()
{
	fio();
	ll t;
	cin>>t;
	while(t--)
	{
		ll n,m;
		cin>>n>>m;
		ll u=max(m-5000,n);//差距
		for(ll i=0;i<=n;i++)
		{
			for(ll j=max(n,m-5000)-u;j<=m-u;j++)
			{
				dp[i][j][0]=dp[i][j][1]=1e18;
			}
		}
		ll d=u;
		dp[n][m-d][0]=dp[n][m-d][1]=0;
		ll ans=1e18;
		for(ll i=n;i>=0;i--)
		{
			for(ll j=m-d;j>=u-d;j--)
			{
				ll k=i-gcd(i,j+d);
				if(k>=0&&i>0)
				{
				dp[k][j][0]=min(dp[k][j][0],dp[i][j][0]+1);
				dp[k][j][1]=min(dp[k][j][1],dp[i][j][0]+1);
				}
				k=j+d-gcd(i,j+d)-d;
				if(k>=0&&j+d>0)
				{
				dp[i][k][0]=min(dp[i][k][0],dp[i][j][1]+1);
				dp[i][k][1]=min(dp[i][k][1],dp[i][j][1]+1);
				}
			}
		}
		if(u+d==0)ans=min({ans,dp[0][0][0],dp[0][0][1]});
		else 
		for(ll i=u-d;i<=m-d;i++)ans=min(ans,dp[0][i][1]+1);
		cout<<ans<<endl;
	}
}