#include <bits/stdc++.h>
using namespace std;
long long int cross(pair<long long int, long long int> o,
                    pair<long long int, long long int> a,
                    pair<long long int, long long int> b) {
  return ((a.first - o.first) * (b.second - o.second) -
          (a.second - o.second) * (b.first - o.first));
}
int n, a, b;
int as = 0;
void ans(int f, int s) {
  if (s == 0) return;
  as += f / s;
  f = f % s;
  swap(f, s);
  ans(f, s);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  while (n--) {
    cin >> a >> b;
    if (a > b)
      ans(a, b);
    else
      ans(b, a);
    cout << as << "\n";
    as = 0;
  }
  return 0;
}
