#include <bits/stdc++.h>
int main() {
  int n;
  std::cin >> n;
  for (int i = 0; i < n; i++) {
    int x, y;
    std::cin >> x >> y;
    int result = 0;
    while (x != 0 && y != 0) {
      if (x > y) {
        result += x / y;
        x = x % y;
      } else if (x < y) {
        result += y / x;
        y = y % x;
      } else {
        result++;
        x -= y;
      }
    }
    std::cout << result << std::endl;
  }
}
