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.
from sys import stdin, stdout
from collections import deque
 
R = lambda : stdin.readline().strip()
RL = lambda : list(map(int, R().split(' '))) 

def fib(n): 
    F = [[1, 1], 
         [1, 0]] 
    if (n == 0): 
        return 0
    power(F, n - 1) 
      
    return F[0][0] 
  
def multiply(F, M): 
  
    x = (F[0][0] * M[0][0] + 
         F[0][1] * M[1][0]) 
    y = (F[0][0] * M[0][1] +
         F[0][1] * M[1][1]) 
    z = (F[1][0] * M[0][0] + 
         F[1][1] * M[1][0]) 
    w = (F[1][0] * M[0][1] + 
         F[1][1] * M[1][1]) 
      
    F[0][0] = x 
    F[0][1] = y 
    F[1][0] = z 
    F[1][1] = w 
  
def power(F, n): 
  
    M = [[1, 1], 
         [1, 0]] 
  
    # n - 1 times multiply the 
    # matrix to {{1,0},{0,1}} 
    for i in range(2, n + 1): 
        multiply(F, M) 
  



T = int(R())
for _ in range(T):
    a,b,n = RL()
    for i in range(100):
        ans = max(fib(i)*a+ fib(i+1)*b,fib(i)*b+ fib(i+1)*a)
        if ans>n:
            print(i)
            break

        

    
    
    
