#include <bits/stdc++.h>

#define int int64_t
using namespace std;

const int MN = 5004;
map<pair<int, int>, int> dp;
const int inf = 1e18;

int f(int a, int b)
{
  if (dp.find({a, b}) != dp.end())
    return dp[{a, b}];

  int g = __gcd(a, b);
  int res;
  if (g == a)
  {
    res = 2;
  }
  else
  {
    res = min(1 + f(a - g, b), 1 + f(a, b - g));
  }

  return dp[{a, b}] = res;
}

void solve()
{
  int a, b;
  cin >> a >> b;

  cout << f(a, b) << "\n";
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}