#include <bits/stdc++.h>
using namespace std;
long long cal(long long x, long long y) {
  long long cnt = 0, a[2] = {x, y};
  sort(a, a + 2);
  while (a[0] > 0) {
    cnt += a[1] / a[0];
    a[1] %= a[0];
    sort(a, a + 2);
  }
  return cnt;
}
int main() {
  long long n, a, b;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a >> b;
    cout << cal(a, b) << endl;
  }
  return 0;
}
