#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
using namespace std;

void solve(int cs) {
  int64_t a, b;
  cin >> a >> b;
  if (a < b) swap(a, b);
  int64_t ans = 0;
  while (a > 0 && b > 0) {
    int64_t d = a - b;
    ans += d / b;
    a -= (d / b) * b;
    if (d / b == 0) {
      ans += 1;
      a = a - b;
    }
    if(a < b) swap(a, b);
  }
  cout << ans << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tc = 1;
  cin >> tc;
  for (int cs = 1; cs <= tc; cs++) {
    solve(cs);
  }
  return 0;
}