#include <bits/stdc++.h>
using namespace std;
int main() {
  int testcases;
  cin >> testcases;
  int arr[testcases];
  for (int i = 0; i < testcases; ++i) {
    long long int a, b, d = 0, counter = 0;
    int flag = 0;
    cin >> a >> b;
    if (a == b) {
      arr[i] = 1;
      continue;
    }
    while (a != b) {
      if (a > b) {
        d = (a - b) / b;
        counter += d;
        a -= d * b;
        if (a == b) {
          counter++;
          arr[i] = counter;
          flag = 1;
          break;
        } else {
          a -= b;
          counter++;
        }
      } else if (b > a) {
        d = (b - a) / a;
        counter += d;
        b -= d * a;
        if (a == b) {
          counter++;
          arr[i] = counter;
          flag = 1;
          break;
        } else {
          b -= a;
          counter++;
        }
      }
    }
    if (flag == 1) continue;
    arr[i] = counter;
  }
  for (int i = 0; i < testcases; ++i) {
    cout << arr[i] << endl;
  }
  return 0;
}
