#include <bits/stdc++.h>
inline long long int no_of_digits(long long int n) {
  return 1 + floor(log10(n));
}
using namespace std;
long long int check(long long int, long long int);
long long int counti;
int main() {
  long long int i, j, k, m, n, q, t, count1, count2, temp1, temp2;
  cin >> n;
  for (i = 0; i < n; i++) {
    cin >> j >> k;
    count1 = 0;
    if (j == k)
      cout << 1 << "\n";
    else {
      while (j != k) {
        if (j == 0 or k == 0) {
          break;
        } else if (j < k) {
          count1 += (k / j);
          k = k - (j * (k / j));
        } else if (k < j) {
          count1 += (j / k);
          j = j - (k * (j / k));
        } else {
          count1++;
          break;
        }
      }
      if (j == k)
        cout << count1 + 1 << "\n";
      else
        cout << count1 << "\n";
    }
  }
  return 0;
}
