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 java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class common {

    public static void main(String[] args) throws java.lang.Exception {
        FastReader sc = new FastReader();
        BufferedWriter w = new BufferedWriter(new PrintWriter(System.out));
       int t=sc.nextInt();
       for(int i=0;i<t;i++)
       {
           long a=sc.nextLong();
           long b=sc.nextLong();
           long n=sc.nextLong();
           if(b>a)
           {
               long temp=b;
               b=a;
               a=temp;
           }
           boolean flag=true;
           int j=0;
           for( j=0;flag;j++)
           {
               if(b<=n&&a<=n)
               {
                   if(j%2==0)
                   {
                       b+=a;
                       //System.out.println("j: "+j+" b: "+b);

                   }
                   else
                   {
                       a+=b;
                       //System.out.println("j: "+j+" a: "+a);
                   }
               }
               else {
                   flag = false;
                   break;
               }
           }
           w.write(j+"\n");
       }
       w.close();

    }

}
class FastReader
{
    BufferedReader br;
    StringTokenizer st;

    public FastReader() throws IOException
    {
        br = new BufferedReader(new
                InputStreamReader(System.in));

    }

    String next() throws NumberFormatException,IOException,NullPointerException
    {
        while (st == null || !st.hasMoreElements())
        {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }

    int nextInt()throws NumberFormatException,IOException,NullPointerException
    {
        return Integer.parseInt(next());
    }

    long nextLong()throws NumberFormatException,IOException,NullPointerException
    {
        return Long.parseLong(next());
    }

    double nextDouble()throws NumberFormatException,IOException,NullPointerException
    {
        return Double.parseDouble(next());
    }

    String nextLine()
    {
        String str = "";
        try
        {
            str = br.readLine();
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
        return str;
    }
}

