#include <bits/stdc++.h>
using namespace std;
int t;
int a, b;
void xuly() {
  int dem = 0;
  while (1) {
    if (a > b) swap(a, b);
    int tam1 = b / a;
    int tam2 = b % a;
    b = tam2;
    dem += tam1;
    if (b == 0) break;
  }
  cout << dem << "\n";
}
int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &a, &b);
    xuly();
  }
  return 0;
}
