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.io.*;
 
 
public class gfg  {

    static PrintWriter out = new PrintWriter(System.out);
    
    public static void main(String[] args) throws IOException{
        //Reader.init(System.in);
        
        Reader.init(System.in);
        int t = Reader.nextInt();
        while(t-->0){
           solve();
        }
            out.close();
    }
    
    static ArrayList<Integer>[] graph; 
    static int n=0;
    static int m=0;
    static boolean[] vis;
    static int[] color;
    static long mod =1000000007;
    static int min=-1;
    static boolean invalid=false;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    static int[] count;
    static int max=0;
    static int total=0;

    static void solve()throws IOException{
        int a = Reader.nextInt();
        int b = Reader.nextInt();
        int target = Reader.nextInt();
        int ans=0;
        while(a<=target && b<=target){
            if(a+b > target){
                ans++;
                break;
            }
            else if(a>=b){
                b+=a;
                ans++;
            }
            else{
                ans++;
                a+=b;
            }
            
        }
        out.println(ans);
    }

    
    static void dfs(int a){ 
        vis[a] = true;
        count[color[a]]++;
        max = Math.max(count[color[a]],max);
        total++;
        for(int i : graph[a]){
           if(!vis[i]){
                dfs(i);    
           }
        }
    }
    

    

    


    
    
    // ggratest common divisor
    static int gcd(int a , int b){
        if(b==0)
            return a;
        else
            return gcd(b,a%b);
    }
 
    // least common multiple
    static int lcm(int a, int b){
        return (a*b)/gcd(a,b);
    }
    
    // a^b
    static long fastpow(long a, long b){
        long res = 1;a=a%mod;
        while(b>0){
            if(b%2==1)
                res = (res*a)%mod;
            a = (a*a)%mod;
            b = b>>1;
        }
        return res;
    }
    
    // priority queue with comparator
    // PriorityQueue<Interval> pq = new PriorityQueue<>(new Comparator<Interval>() {
    //             public int compare(Interval a, Interval b){
    //                 int diff1 = a.r - a.l;
    //                 int diff2 = b.r - b.l;
 
    //                 if(diff1 == diff2){
    //                     return a.l - b.l;
    //                 }
 
    //                 return diff2 - diff1;
    //             }
    // });
}
 
 
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;
 
    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                     new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }
 
    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }
 
    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }
    
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}
class newcomparator implements Comparator<Integer>{
    //@Override
    public int compare(Integer a, Integer  b){
        return a<=b?1:-1;
    }
 }
class node {
    int a;
    long b;// cost to rreach\
    node(int s,long va){
        a=s;
        b=va;
    }
}
class mergesort{
    static void sort(int l, int h, int[] arr){
        if(l<h){
            int mid = (l+h)/2;
            
            sort(l,mid,arr);
            sort(mid+1,h,arr);
            merge(l,mid,h,arr);
        }
    }
    static void merge(int l, int m , int h , int [] arr){
 
        int[] left = new int[m-l+1];
        int[] right = new int[h-m];
        for(int i= 0 ;i< m-l+1;i++){
            left[i] = arr[l+i];
        }
        for(int i=0;i<h-m;i++){
            right[i] = arr[m+1+i];
        }
        //now left and right arrays are assumed to be sorted and we have tp merge them together 
        // int the original aaray.
        int i=l;
        int lindex = 0;
        int rindex =  0;
        
        while(lindex<m-l+1 && rindex<h-m){
            if(left[lindex]>=right[rindex]){
                arr[i]=left[lindex];
                lindex++;
                i++;
            }
            else{
                arr[i]=right[rindex];
                rindex++;
                i++;
            }
        }
        while(lindex<m-l+1){
            arr[i]=left[lindex];
            lindex++;
            i++;
        }
        while(rindex<h-m){
            arr[i]=right[rindex];
            rindex++;
            i++;
        }
    }
    
}



