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.
#include <bits/stdc++.h>
using namespace std;
const long long int Mod = 998244353;
const long long int mod = 1e9 + 7;
const int N = 1e6;
long long int Pow(long long int a, long long int b) {
  a = a % mod;
  long long int res = 1;
  while (b) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return (res % mod);
}
long long int modInverse(long long int a, long long int m) {
  return Pow(a, m - 2);
}
long long int gcd(long long int a, long long int b) {
  return b ? gcd(b, a % b) : a;
}
long long int lcm(long long int a, long long int b) {
  return (a * b) / gcd(a, b);
}
int spf[N + 1], phi[N + 1];
bool prime[N + 1];
void totient() {
  for (int i = 0; i < N + 1; i++) phi[i] = i;
  phi[0] = 0, phi[1] = 1;
  for (int i = 2; i <= N; i++)
    if (phi[i] == i)
      for (int j = i; j <= N; j += i) phi[j] -= phi[j] / i;
}
void use() {
  for (int i = 0; i < N + 1; i++) spf[i] = i;
  for (int i = 2; i <= sqrt(N); i++)
    if (spf[i] == i)
      for (int j = i + i; j <= N; j += i)
        if (spf[j] == j) spf[j] = i;
}
void prm() {
  for (int i = 0; i < N + 1; i++) prime[i] = 1;
  prime[0] = prime[1] = 0;
  for (int i = 2; i <= sqrt(N); i++)
    if (prime[i])
      for (int j = i * i; j <= N; j += i) prime[j] = 0;
}
void solve() {
  long long int a, b, n;
  cin >> a >> b >> n;
  int cnt = 0;
  while (a <= n && b <= n) {
    if (a < b) swap(a, b);
    b += a;
    cnt++;
  }
  cout << cnt << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    solve();
  };
  return 0;
}
