#include <bits/stdc++.h>
int n, a, b, cnt;
int main() {
  std::cin >> n;
  while (n--) {
    std::cin >> a >> b;
    cnt = 0;
    if (a > b) std::swap(b, a);
    while (a && b) {
      cnt += b / a;
      b -= (b / a) * a;
      std::swap(a, b);
    }
    std::cout << cnt << '\n';
  }
  return 0;
}
