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 math import gcd as gc, ceil as cl, floor as fl
from bisect import bisect as bi, bisect_left as bl, bisect_right as br
fibo=[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903]
def GCD(A):
    ret=A[0]
    for i in A:
        ret=gc(ret,i)
    return ret
def solve():
    a,b,n=list(map(int,input().split()))
    if max(a,b)>n:
        print(0)
        return
    if a== max(a,b):
        i=1
        for i in range(1,46):
            if (fibo[i]*a+fibo[i-1]*b)>n:
                print(i)
                return
    else:
        #n-->b
        i=1
        for i in range(1,46):
            if (fibo[i-1]*a+fibo[i]*b)>n:
                print(i)
                return
    
for _ in range(int(input())):
    solve()
