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.Scanner;

public class LuncherDp {
	static Scanner sc =new Scanner(System.in);
	static int dp=0;
	static int c=0;
	static int b=0;
	public static void RodCutter() {
		int n=sc.nextInt();
		int []cost =new int[n+1];
		for(int i=0;i<n;i++) {
			//cost[i]=sc.nextInt();
			cost[i]=i;
		}
		System.out.println(RodCutterBrutForce(cost,n));
		System.out.println(rodCutter(cost,n));
		System.out.println(RodCutterBrutForceHelper(cost,n));
		
	}
	private static int RodCutterBrutForce(int cost[],int n) {
		if(n==0)
			return 0;
		else if(n==1)return cost[1];
		else {
			int max=0;
			//System.out.println(n+"  Brut");
			for(int i=1;i<=n;i++) {
				b++;
				max=Math.max(max,cost[i]+RodCutterBrutForce(cost,n-i));
			}
			return max;
			
		}
			//return Math.max(RodCutterBrutForce(cost,1)+RodCutterBrutForce(cost,n-1), RodCutterBrutForce(cost,2)+RodCutterBrutForce(cost,n-2));
			
	}
	private static int RodCutterBrutForceHelper(int cost[],int n) {
		Integer mask[]=new Integer[cost.length];
		mask[0]=cost[0];
		mask[1]=cost[1];
		return RodCutterBrutForce(cost,n,mask);
		
	}
	private static int RodCutterBrutForce(int cost[],int n,Integer[] mask) {
		if(mask[n]!=null)return mask[n];
		else {
			//System.out.println(n+"   dp");
			int max=0;
				for(int i=1;i<=n;i++) {
					dp++;
					max=Math.max(max,cost[i]+RodCutterBrutForce(cost,n-i,mask));
				}
			mask[n]=max;
			return max;
			
		}
	}

	
    private static int rodCutter(int[] cost, int n){
    	  
	      // Initializing rod array
   
	      int[] rod = new int[n + 1];
      
	      rod[0] = 0;
      
   

	      // Loop for each rod length 'i'
 
	      for(int i = 1; i <= n; i++){
    
		      int maxValue = Integer.MIN_VALUE;

	              // Loop for smaller cut lengths 'j'
     
		      for(int j = 1; j <= i; j++){
          
		      	  // Updating maxValue
              c++;
			  maxValue = Math.max(maxValue, cost[j] + rod[i - j]);

           	       }
	  
          rod[i] = maxValue;

	       }
     

     
      return rod[n];
       }
    
    public static void C() {
    	int t=sc.nextInt();
    	for(int k=0;k<t;k++) {
    		long a=sc.nextLong();
    		long b=sc.nextLong();
    		int n=sc.nextInt();
    		int count=0;
    		boolean f=false;
    		long xa=0;
    		long xb=0;
    		if(a>b) {
    			xa=b;
    			xb=a;
    		}
    		else {
    			xa=a;
    			xb=b;
    		}
    		while(xa<=n&&xb<=n) {
    			if(!f) {
    				xa+=xb;
    			}
    			else {
    				xb+=xa;
    			}
    			f=!f;
    			count++;
    		}
    		System.out.println(count);
    	}
    			
    }
  

	public static void main(String[] args) {
		//System.out.println();
//		RodCutter();
//		System.out.println("c  "+c);
//		System.out.println("dp   "+dp);
//		System.out.println("brut  "+b);
		C();

		

	}

}
