#include <bits/stdc++.h>
using namespace std;
const int N = 1000100;
int main() {
  int n;
  scanf("%d", &n);
  while (n--) {
    int a, b, res = 0;
    scanf("%d %d", &a, &b);
    while (a && b) {
      if (a > b) {
        int x = a / b;
        a -= b * (x);
        res += x;
      } else if (a < b) {
        int x = b / a;
        b -= a * x;
        res += x;
      } else {
        ++res;
        break;
      }
    }
    printf("%d\n", res);
  }
  return 0;
}
