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 math import ceil, log, floor, sqrt
	
def mod_expo(n, p, m):
	"""find (n^p)%m"""
	result = 1
	while p != 0:
		if p%2 == 1:
			result = (result * n)%m
		p //= 2
		n = (n * n)%m
	return result
	
def find_product(n, m, arr):
	"""find |arr i - arr j| mod m"""
	product=1
	if n <= m:
		for i in range(n):
			for j in range(i+1, n):
				 product = (product * abs(arr[i] - arr[j]))%m
		return product
	return 0

def count_moves(a, b, n):
	res = 0
	count = 0
	if a < b:
		c = a
		a = b
		b = c
	res = min(ceil((n+1-a)/b), ceil((n+1-b)/a))
	#print(res)
	while a <= n and b <= n:  
		count += 1
		if count%2 == 0:
			a += b
			res = min(ceil((n+1-a)/b) + count, ceil((n+1-b)/a) + count)
		else:
			b += a
			res = min(ceil((n+1-a)/b) + count, ceil((n+1-b)/a) + count)
		
	return min(count, res)
	
	
def count_tables(l):
	count=0
	l.sort()
	a = l[1]-l[0]
	b = l[2]-l[0]
	if a%3 > 0 and (a%3 + (b - (a - a%3))) >= 3:
		count += 1
	count += l[0] + (2*a)//3
	return int(min(sum(l)/3, l[0] + l[1]))
	
def find_possible_weight(W, arr):
	w = 0
	for i in range(8, 0, -1):
		 count = min(arr[i-1], W//i)
		 w += count * i
		 W -= count * i
		 #print(count)
	return w
	
def find_divisor(a):
	divisors = []
	for i in range(2, min(a, ceil(sqrt(a))+1)):
		if a%i == 0:
			if a/i == i:
				divisors.append(i)
			else:
				divisors.append(i)
				divisors.append(a/i)
	if len(divisors) == 0:
		return -1
	return int(min(divisors))

def find_sum(n, m):
	prod = []
	total, res, index = 0, 0, 0
	for i in range(1, 10):
		prod.append((m*i)%10)
	total = sum(prod)
	res += (n//(10*m)) * total
	n -= (n//(10*m)) * (10*m)
	count = n//m
	while count:
		#print(i)
		res += prod[index]
		count -= 1
		index += 1
	return res
	
t = 1
t = int(input())
while t:
	t = t - 1
	#n = int(input()) 
	a, b, n = map(int, input().split()) 
	#n, m = map(int, input().split())
		#l = list(map(int, input().strip().split()))[:n]
	#str1 = input()
	#if no_vacancy(n, l):
	#	print("Yes")
	#else:
	#	print("No")
	print(count_moves(a, b, n))
