#include <bits/stdc++.h>
using namespace std;
void test() {
  int a, b;
  cin >> a >> b;
  int count = 0;
  if (a > b) {
    a = a + b;
    b = a - b;
    a = a - b;
  }
  int temp;
  while (a > 0 && b > 0) {
    count += b / a;
    temp = b % a;
    b = a;
    a = temp;
  }
  cout << count << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) test();
  return 0;
}
