#include <bits/stdc++.h>
int main() {
  long a, b, c, t, n;
  scanf("%ld", &n);
  while (n--) {
    scanf("%ld %ld", &a, &b);
    if (a > b) {
      t = a;
      a = b;
      b = t;
    }
    c = 0;
    while (1) {
      c += b / a;
      b = b - (b / a) * a;
      if (b <= 0) break;
      t = a;
      a = b;
      b = t;
    }
    printf("%ld\n", c);
  }
  return 0;
}
