#include <bits/stdc++.h>
using namespace std;
long long GCD(long long a, long long b) { return b == 0LL ? a : GCD(b, a % b); }
long long LCM(long long a, long long b) { return a * (b / GCD(a, b)); }
int main() {
  int t;
  cin >> t;
  while (t--) {
    int a, b;
    cin >> a >> b;
    int cnt = 0;
    while (a > 0 && b > 0) {
      if (a > b) swap(a, b);
      if (a == b) {
        cnt++;
        break;
      }
      int x = b - a;
      x = ceil((double)x / (double)a);
      cnt += x;
      x = x * a;
      b -= x;
    }
    cout << cnt << endl;
  }
  return 0;
}
