#include <bits/stdc++.h>
using namespace std;
int main() {
  long long n, x, y, i = 0, cnt = 0, a[1100];
  cin >> n;
  while (n > 0) {
    cin >> x >> y;
    cnt = 0;
    while (n > 0) {
      if (x > y) {
        cnt += (x / y);
        x = x % y;
      } else if (y > x) {
        cnt += (y / x);
        y = y % x;
      }
      if (x == y) {
        y -= x;
        cnt++;
      }
      if (x == 0 || y == 0) break;
    }
    a[i] = cnt;
    i++;
    n--;
  }
  for (int j = 0; j < i; j++) cout << a[j] << "\n";
  return 0;
}
