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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		FastScanner sc=new FastScanner();
		PrintWriter out=new PrintWriter(System.out);
		
		int test = sc.nextInt();
		while(test-->0)
		{
		    int a = sc.nextInt();
		    int b = sc.nextInt();
		    int n = sc.nextInt();
    // 		int []arr = new int[n];
    // 		for(int i=0;i<n;i++)
    // 		   arr[i] = sc.nextInt();
    		   
    		if(Math.max(a, b) > n)
    		   out.println(0);
    		else{
    		    int count=0;
    		    while(Math.max(a, b) <= n){
    		        if(a > b){
    		            b+=a;
    		        }
    		        else{
    		            a+=b;
    		        }
    		        count++;
    		    }
    		    out.println(count);
    		}   
		}
		    
		out.close();
	}
	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;
 
		public FastScanner() {
			try	{
				br = new BufferedReader(new InputStreamReader(System.in));
				st = new StringTokenizer(br.readLine());
			} catch (Exception e){e.printStackTrace();}
		}
 
		public String next() {
			if (st.hasMoreTokens())	return st.nextToken();
			try {st = new StringTokenizer(br.readLine());}
			catch (Exception e) {e.printStackTrace();}
			return st.nextToken();
		}
 
		public int nextInt() {return Integer.parseInt(next());}
 
		public long nextLong() {return Long.parseLong(next());}
 
		public double nextDouble() {return Double.parseDouble(next());}
 
		public String nextLine() {
			String line = "";
			if(st.hasMoreTokens()) line = st.nextToken();
			else try {return br.readLine();}catch(IOException e){e.printStackTrace();}
			while(st.hasMoreTokens()) line += " "+st.nextToken();
			return line;
		}
	}
}




















