#include <bits/stdc++.h>
using namespace std;
int process(int a, int b, int count) {
  if (a == 0 || b == 0)
    return count;
  else if (a > b)
    return process(a % b, b, count + a / b);
  else if (b >= a)
    return process(a, b % a, count + b / a);
}
int main() {
  int T;
  cin >> T;
  for (int i = 0; i < T; i++) {
    int a, b;
    cin >> a >> b;
    cout << process(a, b, 0) << endl;
  }
  return 0;
}
