#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
  int i, a, b, ost, cnt, maxn, minn;
  scanf("%d", &n);
  for (i = 0; i < n; ++i) {
    scanf("%d %d", &a, &b);
    cnt = 0;
    maxn = max(a, b);
    minn = min(a, b);
    while (maxn && minn) {
      ost = maxn % minn;
      cnt += maxn / minn;
      maxn = minn;
      minn = ost;
    }
    printf("%d\n", cnt);
  }
  return 0;
}
