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 bisect import bisect_left
TC = int(input())

fib = {1: 1, 0: 0}


def fib_num(n):
    if n in fib:
        return fib[n]
    else:
        r = fib[n - 1] + fib[n - 2]
        fib[n] = r
        return r


r = 0
i = 0
while r < 10 ** 9 + 1:
    r = fib_num(i)
    i += 1

for tc in range(TC):
    A, B, N = map(int, input().split())
    if A < B:
        A, B = B, A
    delta = A - B

    mini = 1
    maxi = 45

    i = (mini + maxi) // 2
    r = fib_num(i) * B + fib_num(i-1) * delta - N

    while maxi - mini > 1:
        if r < 0:
            mini = i
        else:
            maxi = i

        i = (mini + maxi) // 2
        r = fib_num(i) * B + fib_num(i-1) * delta - N

    r1 = fib_num(mini) * B + fib_num(mini-1) * delta
    r2 = fib_num(maxi) * B + fib_num(maxi-1) * delta

    if r1 > N:
        print(mini - 2)
    else:
        if r2 > N:
            print(maxi - 2)
        else:
            print(maxi - 1)
