#include <bits/stdc++.h>
using namespace std;
int a, b, gcd, n1, n2, n3, n4, cnt1, cnt2, maxi, mini, ans, cnt, ans1, ans2, n;
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &a, &b);
    cnt = 0;
    while (a && b) {
      if (a < b) swap(a, b);
      cnt += a / b;
      a -= a / b * b;
    }
    printf("%d\n", cnt);
  }
}
