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.
t=int(input())
def fib(n):
	if n==1:
		return [0]
	if n==2:
		return [0,1]
	l=[0,1]
	a=0
	b=1
	for i in range(n-1):
		t=a
		a=b
		b+=t
		l.append(b)
	return l
def f(a,b,n):
	i=0
	c=a
	d=b
	while a<=n and b<=n:
		if a<=n and b<=n:
			a+=b
			i+=1
		if a<=n and b<=n:
			b+=a
			i+=1
	j=0
	while c<=n and d<=n:
		if c<=n and d<=n:
			d+=c
			j+=1
		if c<=n and d<=n:
			c+=d
			j+=1
	return min(i,j)
for _ in range(t):
	l=list(map(int, input().split()))
	a=l[0]
	b=l[1]
	n=l[2]
	print(f(a,b,n))