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(x) for x in input().split(' ')][0]
for i in range(T):

    a, b, n = [int(x) for x in input().split(' ')]
    z = 0

    while (max(a, b) <= n):
        z += 1
        if (a < b):
            a += b
        else:
            b += a

    print(z)

"""
fin = open('fixed.in.py', 'r')
fout = open('fixed.out', 'w')


a = fin.readline()
n, k = [int(x) for x in a.split(' ')]

# print(a)

d = []
char = [chr(ord('a') + x) for x in range(26)]

for i in range(n):
    b = fin.readline()
    s = ""
    for x in b:
        if x in char:
            s += x
    d.append(s)

alpha = len(d)

finitestr = []


def rev(st):
    return st[::-1]


def da(ch):
    return d[ord(ch) - ord('a')]


MAXN = 1100

for i in range(n):
    for j in range(len(d[i])):
        if d[i][j] == char[i]:
            # print(char[i], d[i])
            s1 = ""
            t1 = rev(d[i][:j])
            while len(s1) < len(t1):
                if len(s1) >= MAXN:
                    break
                s1 += t1[len(s1)]
                t1 += rev(da(s1[-1]))
            if s1 != t1:
                continue
            s1 = rev(s1)
            t1 = rev(t1)

            s2 = ""
            t2 = d[i][j + 1:]
            while len(s2) < len(t2):
                if len(s2) >= MAXN:
                    break
                s2 += t2[len(s2)]
                t2 += da(s2[-1])
            if s2 == t2:
                finitestr.append(s1 + d[i][j] + s2)

print(finitestr)
finitestr = list(set(finitestr))

print(finitestr)
# print(infinitestr)



dp = [0 for x in range(k + 1)]
dp[0] = 1
for x in range(0, k + 1):
    for g in finitestr:
        if x + len(g) <= k:
            dp[x + len(g)] += dp[x]

ans1 = 0
for x in range(0, k + 1):
    ans1 += dp[x]

fout.write(str(ans1))

# now count infinite strings

numfin = 0
numinf = 0
processed = [0 for x in d]


# print(processed)
print(d)

while (1):
    found = 0
    for i in range(n):
        if processed[i]:
            continue
        if d[i] == "":
            processed[i] = 1
            found = 1
            d = [x.replace(char[i], "") for x in d]
    if found == 0:
        break

print(d)
# print(processed)

for i in range(n):
    if len(d[i]) >= 1 and d[i][0] == char[i]:
        if len(d[i]) == 1:
            numfin = numfin + 1
        else:
            numinf = numinf + 1


print(numfin)
numfin = 0
numfin = len(finitestr)
print(numfin)

# print(numfin)
# print(numinf)

if numfin >= 2:
    fout.write(" -1")
elif numfin == 1:
    if numinf >= 1:
        fout.write(" -1")
    else:
        fout.write(" 1")
elif numfin == 0:
    fout.write(" " + str(numinf))


    # abba ...
    # abbabaabbaababba..:

    # baab ...
    # baababba ...

"""