#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
void DBG() {
  cerr << "]"
       << "\n";
}
template <class H, class... T>
void DBG(H h, T... t) {
  cerr << h;
  if (sizeof...(t)) cerr << ", ";
  DBG(t...);
}
template <class H>
void DBG(vector<H> v) {
  for (int i = 0; i < (int)v.size(); i++) {
    cerr << v[i];
    if (i != (int)v.size() - 1) cerr << ", ";
  }
  cerr << ']' << "\n";
}
constexpr long long MOD = 1e9 + 7;
constexpr long long inf = 1e9 + 7;
void solve(int tc) {
  int a, b, n;
  cin >> a >> b >> n;
  int cnt = 0;
  while (a <= n and b <= n) {
    if (a > b)
      b += a;
    else
      a += b;
    cnt++;
  }
  cout << cnt << "\n";
}
signed main() {
  ios::sync_with_stdio(false), cout.tie(nullptr), cin.tie(nullptr);
  int tc = 0;
  cin >> tc;
  for (int i = 0; i < tc; i++) solve(i + 1);
}

### Prompt

Please formulate a CPP solution to the following problem:

Leo has developed a new programming language C+=. In C+=, integer variables can only be changed with a "+=" operation that adds the right-hand side value to the left-hand side variable. For example, performing "a += b" when a = 2, b = 3 changes the value of a to 5 (the value of b does not change).

In a prototype program Leo has two integer variables a and b, initialized with some positive values. He can perform any number of operations "a += b" or "b += a". Leo wants to test handling large integers, so he wants to make the value of either a or b strictly greater than a given value n. What is the smallest number of operations he has to perform?

Input

The first line contains a single integer T (1 ≤ T ≤ 100) — the number of test cases.

Each of the following T lines describes a single test case, and contains three integers a, b, n (1 ≤ a, b ≤ n ≤ 10^9) — initial values of a and b, and the value one of the variables has to exceed, respectively.

Output

For each test case print a single integer — the smallest number of operations needed. Separate answers with line breaks.

Example

Input


2
1 2 3
5 4 100


Output


2
7

Note

In the first case we cannot make a variable exceed 3 in one operation. One way of achieving this in two operations is to perform "b += a" twice.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
void DBG() {
  cerr << "]"
       << "\n";
}
template <class H, class... T>
void DBG(H h, T... t) {
  cerr << h;
  if (sizeof...(t)) cerr << ", ";
  DBG(t...);
}
template <class H>
void DBG(vector<H> v) {
  for (int i = 0; i < (int)v.size(); i++) {
    cerr << v[i];
    if (i != (int)v.size() - 1) cerr << ", ";
  }
  cerr << ']' << "\n";
}
constexpr long long MOD = 1e9 + 7;
constexpr long long inf = 1e9 + 7;
void solve(int tc) {
  int a, b, n;
  cin >> a >> b >> n;
  int cnt = 0;
  while (a <= n and b <= n) {
    if (a > b)
      b += a;
    else
      a += b;
    cnt++;
  }
  cout << cnt << "\n";
}
signed main() {
  ios::sync_with_stdio(false), cout.tie(nullptr), cin.tie(nullptr);
  int tc = 0;
  cin >> tc;
  for (int i = 0; i < tc; i++) solve(i + 1);
}

```