#include <bits/stdc++.h>
using namespace std;
class subtractions {
 private:
  int _a, _b;
  int _operations;
  bool even_divide(int& a, int& b) {
    if (b > a) {
      if (!(b % a)) {
        _operations += (b / a);
        return true;
      }
    } else if (a >= b) {
      if (!(a % b)) {
        _operations += (a / b);
        return true;
      }
    }
    return false;
  }
  bool quick_divide(int& a, int& b) {
    if (b > a) {
      int factor = b / a;
      b -= a * factor;
      _operations += factor;
      return true;
    } else if (a >= b) {
      int factor = a / b;
      a -= b * factor;
      _operations += factor;
      return true;
    }
    return false;
  }

 public:
  subtractions(int a = 0, int b = 0) : _a(a), _b(b) { _operations = 0; }
  int operate() {
    while (_a > 0 && _b > 0) {
      if (even_divide(_a, _b)) break;
      if (quick_divide(_a, _b)) continue;
      ++_operations;
    }
    return _operations;
  }
};
int main() {
  int tests = 0;
  cin >> tests;
  while (tests > 0) {
    int a, b;
    cin >> a >> b;
    subtractions s(a, b);
    cout << s.operate() << endl;
    --tests;
  }
  return 0;
}
