You've got two numbers. As long as they are both larger than zero, they go through the same operation: subtract the lesser number from the larger one. If they equal substract one number from the another. For example, one operation transforms pair (4,17) to pair (4,13), it transforms (5,5) to (0,5).

You've got some number of pairs (ai, bi). How many operations will be performed for each of them?

Input

The first line contains the number of pairs n (1 ≤ n ≤ 1000). Then follow n lines, each line contains a pair of positive integers ai, bi (1 ≤ ai, bi ≤ 109).

Output

Print the sought number of operations for each pair on a single line.

Examples

Input

2
4 17
7 987654321


Output

8
141093479
#include <bits/stdc++.h>
using namespace std;
long long ESP = 1e18;
bool isPrime(long long n) {
  if (n == 0 || n == 1) return false;
  if (n == 2) return true;
  for (long long i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}
bool anagram(char *s1, char *s2) {
  long long count[256];
  memset(count, 0, sizeof(count));
  long long i;
  for (i = 0; s1[i] && s2[i]; i++) {
    count[s1[i]]++;
    count[s2[i]]--;
  }
  if (s1[i] || s2[i]) {
    return false;
  }
  for (int(i) = 0; i < 256; ++i) {
    if (count[i]) {
      return false;
    }
  }
  return true;
}
int find_largest_digit(int n) {
  int mx = 0;
  while (n > 0) {
    mx = max(mx, n % 10);
    n /= 10;
  }
  return mx;
}
long long no_of_digits(long long n) {
  long long ans = 0;
  while (n > 0) {
    ans++;
    n /= 10;
  }
  return ans;
}
long long moduloMultiplication(long long a, long long b, long long zz) {
  long long res = 0;
  a %= zz;
  while (b) {
    if (b & 1) res = (res + a) % zz;
    a = (2 * a) % zz;
    b >>= 1;
  }
  return res;
}
long long to_int(string s) {
  bool o = true;
  long long ans = 0;
  for (long long i = 0; i < s.length(); i++) {
    ans = ans * 10 + (s[i] - 48);
  }
  return ans;
}
inline long long powmod(long long x, long long n, long long m) {
  if (n == 0 || x == 1)
    return 1;
  else if (n % 2 == 0) {
    return powmod((x * x) % m, n / 2, m);
  } else {
    return x * (powmod((x * x) % m, (n - 1) / 2, m)) % m;
  }
}
long long poww(long long a, long long b) {
  if (b == 0 || a == 1) return 1;
  long long half = poww(a, (b / 2));
  if (half < 0 || half > ESP) return -1;
  long long full = (half * half);
  if (half != 0 && full / half != half) {
    return -1;
  }
  if (b % 2) {
    if (full * a < 0 || full * a > ESP) return -1;
  }
  if (full < 0 || full > ESP) return -1;
  if (b % 2) {
    long long x = a * full;
    if (a != 0 && x / a != full) {
      return -1;
    }
    return (x);
  }
  return full;
}
long long invmod(long long a, long long modulo) {
  long long check = powmod(a, modulo - 2, modulo) % modulo;
  return check;
}
long long max(long long a, long long b) {
  if (a > b) {
    return a;
  }
  return b;
}
long long min(long long a, long long b) {
  if (a < b) {
    return a;
  }
  return b;
}
long long min(long long a, int b) {
  if (a < b) return a;
  return b;
}
long long min(int a, long long b) {
  if (a < b) return a;
  return b;
}
long long max(long long a, int b) {
  if (a > b) return a;
  return b;
}
long long max(int a, long long b) {
  if (a > b) return a;
  return b;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
void yes() {
  cout << "YES"
       << "\n";
}
void no() {
  cout << "NO"
       << "\n";
}
vector<int> factorize(int n) {
  vector<int> res;
  for (int i = 2; i * i <= n; ++i) {
    while (n % i == 0) {
      res.push_back(i);
      n /= i;
    }
  }
  if (n != 1) {
    res.push_back(n);
  }
  return res;
}
void printDivisors(int n) {
  for (int i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
      if (n / i == i)
        printf("%d ", i);
      else
        printf("%d %d ", i, n / i);
    }
  }
}
int phi(int n) {
  int result = n;
  for (int p = 2; p * p <= n; ++p) {
    if (n % p == 0) {
      while (n % p == 0) n /= p;
      result -= result / p;
    }
  }
  if (n > 1) result -= result / n;
  return result;
}
bool presents(vector<long long> v, int x) {
  bool flag = false;
  for (decltype(v.begin()) it = v.begin(); it != v.end(); it++) {
    if (*it == x) flag = true;
  }
  return flag;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  while (n--) {
    long long a, b;
    cin >> a >> b;
    long long mx = max(a, b);
    long long mn = min(a, b);
    long long ans = 0;
    while (mx > 0 and mn > 0) {
      ans += mx / mn;
      long long k = mx;
      mx = mn;
      mn = k % mn;
    }
    cout << ans << "\n";
    ;
  }
  return 0;
}
