#include <bits/stdc++.h>
using namespace std;
int get() {
  int f = 0, v = 0;
  char ch;
  while (!isdigit(ch = getchar()))
    if (ch == '-') break;
  if (ch == '-')
    f = 1;
  else
    v = ch - 48;
  while (isdigit(ch = getchar())) v = v * 10 + ch - 48;
  if (f == 1) return -v;
  return v;
}
long long calc(int a, int b) {
  if (a == 0) return 0;
  return calc(b % a, a) + b / a;
}
int main() {
  int T = get();
  for (int i = 1; i <= T; i++) {
    int a = get(), b = get();
    cout << calc(a, b) << endl;
  }
  return 0;
}
