#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int n, a, b, res, t;
int main() {
  cin >> n;
  for (long i = 1; i <= n; i++) {
    cin >> a >> b;
    res = 0;
    if (a < b) {
      t = b;
      b = a;
      a = t;
    }
    while (a > 0 && b > 0) {
      t = a - b;
      res += t / b + 1;
      int tmp = a;
      a = b;
      b = tmp - (t / b + 1) * b;
    }
    cout << res << "\n";
  }
}
