#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long n) {
  if (n <= 1) return false;
  for (long long i = 2; i <= floor(sqrt(n)); i++)
    if (n % i == 0) return false;
  return true;
}
long long factorial(int n) {
  long long x = 1e9 + 7;
  long long fact = 1, i;
  for (i = 1; i <= n; i++) fact = (fact * i) % x;
  return fact;
}
int main() {
  int n, i;
  cin >> n;
  long long a[n], b[n], count, larger, smaller;
  for (i = 0; i < n; i++) cin >> a[i] >> b[i];
  for (i = 0; i < n; i++) {
    count = 0;
    larger = max(a[i], b[i]);
    smaller = min(a[i], b[i]);
    while (1) {
      if (larger == 1) {
        count += smaller;
        break;
      } else if (smaller == 1) {
        count += larger;
        break;
      } else if (larger == smaller) {
        count++;
        break;
      } else if (larger == 0 || smaller == 0)
        break;
      else {
        count += larger / smaller;
        larger = larger % smaller;
        if (larger < smaller) swap(larger, smaller);
      }
    }
    cout << count << "\n";
  }
  return 0;
}
