#include <bits/stdc++.h>
using namespace std;
int n, i, x, y, c, k, q, j;
int main() {
  scanf("%d", &n);
  while (n) {
    scanf("%d %d", &x, &y);
    c = 0;
    while (x && y) {
      if (x > y) {
        c += x / y;
        x %= y;
      } else {
        c += y / x;
        y %= x;
      }
    }
    printf("%d\n", c);
    n--;
  }
}
