#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  while (n--) {
    int a, b;
    cin >> a >> b;
    int ans = 0;
    int mn = min(a, b), mx = max(a, b);
    int ansmn = mn, ansmx = mx;
    do {
      ans += (mx / mn);
      mx %= mn;
      ansmn = min(mx, mn);
      ansmx = max(mx, mn);
      mn = ansmn;
      mx = ansmx;
    } while (mx && mn);
    cout << ans << endl;
  }
}
