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.
#!/usr/bin/env python3
'''
                     ........'.....
                   ...            ....
                   .      ;xc        ..
                  .    cdokk'         .
                 .    .dOOOd:,.       .
                ..     .xOxok0c      ..
               .,',....,ox' .;.      ..
              .:. .........''.       .
              ..   ... .''   .'.     .
             .;,.  ....        .'.  ..
             .'lc,.     .,;;:c'  .,.'.
            ' .clc;.  .,':::'.     ',
              'lo;'.  , .lc:c    .,;.
           .   .. '.  '  ....    'cc
          .      ''   '          'l'
         ',.  ...'  ..''         ..
        .:.  .' .'..'.....     ....
        .'  .'           '.    .. .
        .   ,.           .,    ....
        .. .'  .........  '     .'
         ' .'            '.    ..
          . .            .    ..
          ..                 ..
 _                _    _                 _ _   _
| |_ _ _ ___ _  _| |__| |___ ___ __ __ _(_) |_| |_
|  _| '_/ _ \ || | '_ \ / -_|_-< \ V  V / |  _| ' \
 \__|_| \___/\_,_|_.__/_\___/__/  \_/\_/|_|\__|_||_|
 _   _          _                _
| |_| |_  ___  | |_  ___ __ _ __| |
|  _| ' \/ -_) | ' \/ -_) _` / _` |
 \__|_||_\___| |_||_\___\__,_\__,_|

'''
PUTIN_HELP_ME            = not None
NAVALNY_HELP_ME          = not None
DURKA_HELP_ME            = not None

import sys, os, re
from math import *
from random import *

class Answer(BaseException):
	def __init__(self, txt):
		self.__text = txt
	def what(self):
		return self.__text
def answer(arg):
	raise Answer
def lcm(a, b: int):
	return a * b // gcd(a, b)
def readArr(modifier=int):
    return list(map(modifier, input().split()))
def rA(m=int):
    return readArr(m)
    
def chomp(s: str):
    return (s[:-1] if s[-1] == '\n' else s)
def readFile(name: str):
    f = open(name, "r");
    r = f.readlines();
    f.close()
    return r
def init_all():
    sys.setrecursionlimit(max(sys.getrecursionlimit(), 500000))

def lower_bound(a, k):
    l, r = 0, len(a) - 1
    while l != r:
        mid = (l + r) // 2
        if a[mid] < k:
            l = mid + 1
        else:
            r = mid
    return l

def upper_bound(a, k):
    l, r = 0, len(a) - 1
    while l + 1 < r:
        mid = (l + r) // 2
        if a[mid] <= k:
            l = mid
        else:
            r = mid - 1
    if a[r] == k:
        return r
    else:
        return l

class poly_hash:
    def __init__(self, s):
        self.seed = 228
        self.M = 1000000007
        self.n = len(s)
        self.pows = [1]
        self.hsh = [0 for _ in range(self.n + 1)]        
        for _ in range(self.n):
            self.pows.append(self.pows[-1] * self.seed % self.M)
        for i in range(self.n):
            self.hsh[i + 1] = (self.hsh[i] * self.seed + s[i]) % self.M
    def sub_hash(self, l, r):
        return (self.hsh[r] - self.hsh[l] * self.pows[r - l]) % self.M


def pre_func(s):
    p = [0]
    a = 0
    for i in range(1, len(s)):
        while a > 0 and s[i] != s[a]:
            a = p[a - 1]
        if s[i] == s[a]:
            a += 1
        p.append(a)
    return p

def solve():
    a, b, n = readArr()
    if a > b:
        a, b = b, a
    ans = 0
    while max(a, b) <= n:
        ans += 1
        a += b
        a, b = b, a
    print(ans)

def main(argv: list):
    init_all()
    t = 1
    t = int(input())
    for _ in range(t):
        try:
            solve()
        except Answer as a:
            print(a.what())
    return 0

if __name__ == "__main__":
    exit(main(sys.argv))
