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.
#CF-650 (DIV-3)

'''test=int(input())
for i in range(test):
    b=input()
    ans=""
    if len(b)==2:
        ans=b
    else:
        ans+=b[0]
        j=1
        while j<len(b)-1:
            ans+=b[j]
            j+=2
        ans+=b[-1]
    print(ans)
'''
'''test=int(input())
for i in range(test):
    n=int(input())
    arr=[int(i) for i in input().split()]
    type1=0
    type2=0
    for i in range(n):
        if i%2==0 and arr[i]%2==1:
            type1+=1
        elif i%2==1 and arr[i]%2==0:
            type2+=1
    if type1!=type2:
        print(-1)
    else:
        print(type1)'''


'''test=int(input())
for i in range(test):
    n,k=[int(i) for i in input().split()]
    binary=input()
    suff=[float("inf")]*(n)
    suff[-1]=0 if binary[-1]=="1" else float("inf")
    for j in range(len(binary)-2,-1,-1):
        if binary[j]=="1":
            suff[j]=0
        else:
            suff[j]=1+suff[j+1]
    last=-1
    ans=0
    for i in range(len(binary)):
        if binary[i]=="0":
            if last!=-1:
                if i-last>k and suff[i]>k:
                    ans+=1
                    last=i
            elif suff[i]>k:
                ans+=1
                last=i
        else:
            last=i
    print(ans)'''


'''test=int(input())
for i in range(test):
    import heapq
    s=input()
    m=int(input())
    arr=[int(i) for i in input().split()]
    s=sorted("".join([i for i in s]))
    heap=[]
    for i in range(m):
        heapq.heappush(heap,(arr[i],i))
    ans=[""]*(m)
    t=0
    while heap:
        a,b=heapq.heappop(heap)
        while True:
            sum_=0
            for i in range(m):
                if ans[i]!="":
                    sum_+=abs(b-i)
            if sum_==a:
                break
            else:
                t+=1
        ans[b]=s[t]
    print("".join(ans))'''

#CODEFORCES GLOBAL ROUND

test=int(input())
for i in range(test):
    a,b,n=[int(i) for i in input().split()]
    ans=0
    while a<=n and b<=n:
        if a>=b:
            b+=a
        else:
            a+=b
        ans+=1
    print(ans)