#include <bits/stdc++.h>
using namespace std;
long long fx[4] = {1, -1, 0, 0};
long long fy[4] = {0, 0, 1, -1};
int smallest(int x, int y, int z) {
  int c = 0;
  while (x && y && z) {
    x--;
    y--;
    z--;
    c++;
  }
  return c;
}
bool rs(long long a, long long b) { return (a > b); }
int main() {
  long long t;
  cin >> t;
  while (t--) {
    long long a, b;
    cin >> a >> b;
    long long mini = min(a, b);
    long long maxi = max(a, b);
    long long ans = 0;
    while (maxi > 0 && mini > 0) {
      long long r = maxi % mini;
      ans += (maxi / mini);
      maxi = mini;
      mini = r;
    }
    cout << ans << endl;
  }
  return 0;
}
