#include <bits/stdc++.h>
using namespace std;
int in() {
  int n;
  scanf("%d", &n);
  return n;
}
long long Lin() {
  long long n;
  scanf("%lld", &n);
  return n;
}
double Din() {
  double n;
  scanf("%lf", &n);
  return n;
}
const long long inf = 1e17;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
int sum(int a, int b) {
  if (a == 0 || b == 0) return 0;
  return a / b + sum(b, a % b);
}
int main() {
  int n = in();
  while (n--) {
    int a = in(), b = in();
    if (a < b) swap(a, b);
    printf("%d\n", sum(a, b));
  }
  return 0;
}
