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.
import math



def dtod(a):
     s=''
     while a!=0:
          s+=str(a%2)
          a=int(a/2)
     return s[::-1]


'''
n=int(input())
for i in range(n):
     s=input().split(' ')
     a=int(s[0])
     b=int(s[1])
     _min=min(a,b)
     _max=max(a,b)
     if _max%_min!=0:
          print('-1')
     else:
          f=False
          s=dtod(int(_max/_min))
          for ii in range(len(s)):
               if (ii>0 and s[ii]!='0'):
                    f=True
          if(f):
               print('-1')
          else:
               a_2=0
               for ii in range(len(s)):
                    if(s[ii]=='0'):
                         a_2+=1
               print(int(math.ceil((a_2)/3)))
               
'''
'''
t=int(input())
for k in range(t):
     s=input().split(' ')
     n=int(s[0])
     m=int(s[1])
     a=[]
     for i in range(n):
          s=input().split(' ')
          b=[]
          for c in s:
               b.append(int(c))
          a.append(b)
     savecellbyhorizontal=m
     savecellbyvertical=n
     for i in range(n):
          for j in range(m):
               if a[i][j]==1:
                    savecellbyvertical-=1
                    break
     for j in range(m):
          for i in range(n):
               if a[i][j]==1:
                    savecellbyhorizontal-=1
                    break
     if(min(savecellbyhorizontal,savecellbyvertical)%2==0):
          print('Vivek')
     else:
          print('Ashish')
     #print(str(savecellbyvertical)+' '+str(savecellbyhorizontal))
     #print(a)
'''
q = int(input())
for qw in range(q):
     s = input().split(' ')
     a = int(s[0])
     b = int(s[1])
     n = int(s[2])
     o = 0
     while (a > n or b > n) == False:
          if a < b:
               a += b
          else:
               b += a
          o += 1
     print(o)
