#define LOCAL
#include <bits/stdc++.h>
#define fir first
#define sec second
#define el '\n'

#ifdef LOCAL
#define FINISH cerr << "FINISH" << endl;
#else
#define FINISH ;
#endif

#ifdef LOCAL
#define debug(x) cerr << setw(4) << #x << " == " << x << endl
#else
#define debug(x)
#endif

#ifdef LOCAL
#define debugv(x)                   \
    cerr << setw(4) << #x << ":: "; \
    for (auto i : x)                \
        cerr << i << " ";           \
    cerr << endl
#else
#define debugv(x)
#endif

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
ostream& operator<<(ostream& out, PII& x)
{
    out << x.fir << " " << x.sec << endl;
    return out;
}

const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int N = 200020;
void solve()
{
    ll a, b;
    cin >> a >> b;
    queue<array<ll, 3>> q;
    ll g = __gcd(a, b);
    a = a / g, b = b / g;
    q.push({a, b, 0});
    ll ans = inf;
    while (!q.empty()) {
    	auto [x, y, s] = q.front();
    	// cout << x << " " << y << " " << s << endl;
    	if (s + 2 >= ans) {
    		break;
    	}
    	q.pop();
    	if (__gcd(x, y) == x) {
    		ans = min(ans, s + 2);
    		continue;
    	}
    	if (__gcd(x - 1, y) != 1) {
    		ll xx = x - 1, yy = y;
    		g = __gcd(xx, yy);
    		xx /= g, yy/= g;
    		q.push({xx, yy, s + 1});
    	}
    	if (__gcd(x, y - 1) != 1) {
    		ll yy = y - 1, xx = x;
    		g = __gcd(xx, yy);
    		xx /= g, yy/= g;
    		q.push({xx, yy, s + 1});
    	}
    	if (__gcd(x - 1, y - 1) != 1) {
    		ll xx = x-1, yy = y - 1;
    		g = __gcd(xx, yy);
    		xx /= g, yy/= g;
    		q.push({xx, yy, s + 2});
    	}
    }
    cout << ans << el;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}