#include <bits/stdc++.h>
const int BIG = 2000000000;
const double INF = 1e9;
const double EPS = 1e-9;
using namespace std;
int main() {
  int n, a, b;
  scanf("%d", &n);
  while (n--) {
    scanf("%d%d", &a, &b);
    int ans = 0;
    int temp;
    if (a < b) {
      temp = b;
      b = a;
      a = temp;
    }
    while (a > 0 && b > 0) {
      ans += a / b;
      a %= b;
      temp = a;
      a = b;
      b = temp;
    }
    printf("%d\n", ans);
  }
  return 0;
}
