#include <bits/stdc++.h>
using namespace std;
const double pi =
    3.14159265358979323846264338327950288419716939937510582097494459;
int dX[] = {0, 1, 0, -1, 1, 1, -1, -1};
int dY[] = {1, 0, -1, 0, 1, -1, 1, -1};
string alpha = "abcdefghijklmnopqrstuvwxyz";
const int N = 200200;
void solve() {
  int n, a, b, ans, q;
  cin >> n;
  while (n--) {
    ans = 0;
    q = 1;
    cin >> a >> b;
    while (q != 0) {
      ans += max(a, b) / min(a, b);
      q = max(a, b) - ((max(a, b) / min(a, b)) * min(a, b));
      if (max(a, b) == a)
        a = q;
      else
        b = q;
    }
    cout << ans << endl;
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  solve();
  return 0;
}
