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 sys
sys.setrecursionlimit(10000)
# default is 1000 in python


t = int(input())
# t = 1

for _ in range(t):

	a, b, n = list(map(int, input().split()))

	large = max(a,b)
	small = min(a,b)

	ans = 0
	newans = large
	while newans <= n:
		ans += 1
		large = newans
		newans += small
		small = large
	print(ans)



# try:
	# raise Exception
# except:
	# print("-1")
	

# thenos.sort(key=lambda x: x[2], reverse=True)

# int(math.log(max(numbers)+1,2))

# 2**3 (power)

# a,t = (list(x) for x in zip(*sorted(zip(a, t))))

# to copy lists use .copy()

# pow(p, si, 1000000007) for modular exponentiation

# my_dict.pop('key', None)
# This will return my_dict[key] if key exists in the dictionary, and None otherwise.



# bin(int('010101', 2))
