#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const long long oo = 0x3f3f3f3f3f3f3f3fll;
const double eps = 1e-6;
const int N = 1000010;
long long dfs(int a, int b) {
  if (a > b) swap(a, b);
  if (a == 0) return 0;
  return dfs(b % a, a) + b / a;
}
int main() {
  int ca;
  for (scanf("%d", &ca); ca--;) {
    int a, b;
    scanf("%d%d", &a, &b);
    cout << dfs(a, b) << endl;
  }
  return 0;
}
