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;
class Debugger {
 public:
  Debugger(const std::string& _separator = ", ")
      : first(true), separator(_separator) {}
  template <typename ObjectType>
  Debugger& operator,(const ObjectType& v) {
    if (!first) cerr << separator;
    cerr << v;
    first = false;
    return *this;
  }
  ~Debugger() { cerr << "\n"; }

 private:
  bool first;
  string separator;
};
template <typename T1, typename T2>
inline ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
inline ostream& operator<<(ostream& os, const vector<T>& v) {
  bool first = true;
  os << "[";
  for (unsigned long long i = 0; i < v.size(); i++) {
    if (!first) os << ", ";
    os << v[i];
    first = false;
  }
  return os << "]";
}
template <typename T>
inline ostream& operator<<(ostream& os, const set<T>& v) {
  bool first = true;
  os << "[";
  for (typename set<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "]";
}
template <typename T1, typename T2>
inline ostream& operator<<(ostream& os, const map<T1, T2>& v) {
  bool first = true;
  os << "[";
  for (typename map<T1, T2>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "]";
}
long long T;
long long gcd(long long a, long long b, long long cnt) {
  if (a < b) swap(a, b);
  while (b != 0) {
    long long cis = a - (a / b) * b;
    cnt += (a / b);
    a = cis;
    swap(a, b);
    if (a < b) swap(a, b);
  }
  return cnt;
}
int main() {
  ios_base::sync_with_stdio(0);
  ;
  cin >> T;
  while (T--) {
    long long a, b;
    cin >> a >> b;
    cout << gcd(a, b, 0) << "\n";
  }
  return 0;
}
