#include <bits/stdc++.h>

#define int int64_t
using namespace std;

const int MN = 5004;
int dp[MN][MN];
const int inf = 1e18;

void solve()
{
  int a, b;
  cin >> a >> b;
  int gg = __gcd(a, b);
  for (int i = 0; i < MN; ++i)
    dp[i][0] = 1;
  dp[0][0] = 0;

  for (int g = a; g >= gg; --g)
  {
    for (int aog = 1; g * aog <= a; ++aog)
    {
      int ca = aog * g;
      int cb = b - (b % g);
      int tmpg = __gcd(ca, cb);
      int tmpaog = ca / tmpg;
      dp[g][aog] = dp[tmpg][tmpaog - 1] + 1;

      for (int g2 = tmpg + tmpg; g2 <= ca; g2 += tmpg)
        if (ca % g2 == 0)
        {
          /*for(int aog2=0; g2*aog2<=ca; ++aog2) {
            int a2 = g2*aog2;
            int d = (ca-a2)/g + (cb%g2)/g;
            dp[g][aog] = min(dp[g][aog], d+dp[g2][aog2]);
          }*/
          int aog2 = ca / g2;
          int d = (cb % g2) / tmpg;
          dp[g][aog] = min(dp[g][aog], d + dp[g2][aog2]);
        }
      // cerr<<"dp["<<g<<"]["<<aog<<"]= "<<dp[g][aog]<<'\n';
    }
  }

  cout << dp[gg][a / gg] << '\n';
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}