#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  while (n > 0) {
    int x, y, Sum = 0;
    cin >> x >> y;
    if (x < y) swap(x, y);
    while (y != 0) {
      Sum += x / y;
      x %= y;
      if (x < y) swap(x, y);
    }
    cout << Sum << endl;
    n--;
  }
  return 0;
}
