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 sys import stdin,stdout
# from math import pi
# from collections import deque
# from heapq import heappush,heappop
Pi = lambda x: stdout.write(str(x) + '\n')
Ps = lambda x: stdout.write(str(x))
S = lambda x: x*(x+1) // 2
I = lambda x: 1+(2*x)
R = lambda:stdin.readline()
Ri = lambda x:map(int,x.split())
Rs = lambda x:map(str,x.split())
Rf = lambda x:map(float,x.split())
char = lambda x,y:ord(x) - ord(y) 
gcd = lambda a,b: a if b==0 else gcd(b, a%b) 
lcm = lambda a,b: a * b // gcd(a, b)
# find = lambda u,par: u if u==par[u] else find(par[u],par)
distance = lambda a,b,c,d: ((a-c)**2) + ((b-d)**2)
# distance = lambda a,b,c,d: (abs(a-c)) + (abs(b-d))
MaxN = int(1e6) + 10
mod = int(1e9) + 7
# global fx,fy
# fx = [-2, -2, -1, -1,  1, 1,  2, 2]
# fy = [-1,  1, -2,  2, -2, 2, -1, 1]
# fx,fy = [0,0,-1,1],[1,-1,0,0]
def f(i,n,dp,inc,A):
	if dp[i]!=-1:return dp[i]
	ans = 0
	for j in range(i+inc,n,inc):
		if A[j] < A[i]:
			ans = max(ans, f(j,n,dp,inc,A) + 1)
	dp[i] = ans
	return dp[i]

def main():			

	for x in stdin:		
		if x=='\n':continue
		cases = int(x)
		for t in range(cases):
			a,b,n = Ri(R())
			if a+b > n:
				Pi(1)
			else:
				ans = 0
				if a>b:
					a,b = b,a
				while max(a,b)<=n:
					ans += 1
					if ans&1:
						a += b
					else:
						b += a
					# print(a,b)
				Pi(ans)
if __name__ == '__main__':
	main()
