#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 = 1 + f(a - g, b);

    int mini = -1;
    for (int g2 = g + g; g2 <= a; g2 += g)
    {
      if (a % g2 == 0)
      {
        if (mini == -1 || b % g2 < b % mini)
          mini = g2;
      }
    }
    assert(mini != -1);
    res = min(res, (b % mini) / g + f(a, b - (b % mini)));
  }

  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;
}