#include <bits/stdc++.h>
using namespace std;
long long t;
int main() {
  cin >> t;
  while (t--) {
    long long a, b;
    cin >> a >> b;
    long long dem = 0;
    if (a > b) swap(a, b);
    if (a != 0) dem += b / a;
    if (a != 0) b -= 1ll * a * (b / a);
    if (b != 0) dem += a / b;
    if (b != 0) a -= 1ll * b * (a / b);
    while (a != 0 && b != 0) {
      if (b >= a && a != 0) {
        dem += b / a;
        b -= 1ll * a * (b / a);
      }
      if (a >= b && b != 0) {
        dem += a / b;
        a -= 1ll * b * (a / b);
      }
    }
    cout << dem << endl;
  }
}
