#include <bits/stdc++.h>
using namespace std;
struct sort_pred {
  bool operator()(const pair<string, int> &left,
                  const pair<string, int> &right) {
    return left.second > right.second;
  }
};
string str(int i) {
  std::stringstream ss;
  std::string s;
  ss << i;
  s = ss.str();
  return s;
}
vector<std::string> split(std::string text) {
  std::istringstream is(text);
  std::string word;
  std::vector<std::string> vs;
  while (is >> word) vs.push_back(word);
  return vs;
}
unsigned int divisors(unsigned long int n) {
  unsigned short int primes[10000];
  for (unsigned int i = 0; i < 10000 && i <= n; i++) primes[i] = 0;
  unsigned short int how_many = 1;
  for (unsigned long int i = 2; i < 10000 && i <= n; i++) {
    while (!(n % i)) {
      n /= i;
      primes[i]++;
    }
    if (primes[i]) how_many *= (primes[i] + 1);
  }
  return how_many;
}
string alph = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
int Contains(char c) {
  for (int j = (0); j < (int)(alph.length()); j++)
    if (c == alph[j]) return 1;
  return 0;
}
int find(int x, int y) {
  int count = 0, tmp = 0;
  while (x != y && x > 0 && y > 0) {
    tmp = 0;
    if (x < y) {
      tmp = (y - x) / x;
      y = y - tmp * x;
    } else {
      tmp = (x - y) / y;
      x = x - tmp * y;
    }
    if (x > y && x > 0 && y > 0) {
      x = x - y;
      count++;
    } else if (x < y && x > 0 && y > 0) {
      y = y - x;
      count++;
    }
    count += tmp;
  }
  return count + 1;
}
int main() {
  long long int n, a, b;
  vector<long long int> ans;
  cin >> n;
  for (int i = (0); i < (int)(n); i++) {
    int tmp = 0;
    cin >> a >> b;
    ans.push_back(find(a, b) + tmp);
  }
  for (int i = (0); i < (int)(n); i++) cout << ans[i] << endl;
  return 0;
}
