#include <bits/stdc++.h>
int main() {
  long long int tc, n1, n2, c;
  scanf("%lld", &tc);
  long long int i;
  while (tc--) {
    c = 0;
    scanf("%lld%lld", &n1, &n2);
    while ((n1) && (n2)) {
      if (n1 < n2) {
        c = c + n2 / n1;
        n2 = n2 % n1;
      } else {
        c = c + n1 / n2;
        n1 = n1 % n2;
      }
    }
    printf("%d\n", c);
  }
}
