#include <bits/stdc++.h>
using namespace std;
int main() {
  int t, a, b;
  cin >> t;
  while (t--) {
    cin >> a >> b;
    int c, d;
    c = max(a, b);
    d = min(a, b);
    int ans = 0;
    while (!(c == 0 || d == 0)) {
      ans += (c / d);
      c = c % d;
      swap(c, d);
    }
    std::cout << ans << std::endl;
  }
  return 0;
}
