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.
//package cf;
import java.io.*;
import java.util.*;

public final class Cf {

    public static void main(String[] args) throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(java.io.FileDescriptor.out), "ASCII"), 512);        
        Reader sc = new Reader();
        int tc=sc.nextInt();
        long a,b,k,sum;
        while(tc-->0){
            a=sc.nextLong();
            b=sc.nextLong();
            sum=sc.nextLong();
            k=0;
            if(a>b){
                long temp=a;
                a=b;
                b=temp;
            }
         while(a<=sum&&b<=sum)
        {
          if(k%2==0){a+=b;}
          else {b+=a;}
          k++;  
       }
       out.write(k+"\n");
        }
        out.flush();
        
    }
    public static void debug(String s)
    {
        System.out.println(s);
    }

    ///////////////////////////////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////////////////////////////
    static class FastReader {        
        
        BufferedReader br;        
        StringTokenizer st;        
        
        public FastReader() {            
            br = new BufferedReader(new InputStreamReader(System.in));            
        }        
        
        String next() {            
            while (st == null || !st.hasMoreElements()) {                
                try {                    
                    st = new StringTokenizer(br.readLine());                    
                } catch (IOException e) {                    
                    e.printStackTrace();                    
                }                
            }            
            return st.nextToken();            
        }        
        
        int nextInt() {            
            return Integer.parseInt(next());            
        }        
        
        long nextLong() {            
            return Long.parseLong(next());            
        }        
        
        double nextDouble() {            
            return Double.parseDouble(next());            
        }        
        
        String nextLine() {            
            String str = "";            
            try {                
                str = br.readLine();                
            } catch (IOException e) {                
                e.printStackTrace();                
            }            
            return str;            
        }        
    }
    //////////////////////////////////////////////////////////////////

    static class Reader {        

        final private int BUFFER_SIZE = 1 << 16;        
        private DataInputStream din;        
        private byte[] buffer;        
        private int bufferPointer, bytesRead;        
        
        public Reader() {            
            din = new DataInputStream(System.in);            
            buffer = new byte[BUFFER_SIZE];            
            bufferPointer = bytesRead = 0;            
        }        
        
        public Reader(String file_name) throws IOException {            
            din = new DataInputStream(new FileInputStream(file_name));            
            buffer = new byte[BUFFER_SIZE];            
            bufferPointer = bytesRead = 0;            
        }        
        
        public String readLine() throws IOException {            
            byte[] buf = new byte[1002]; // line length 
            int cnt = 0, c;            
            while ((c = read()) != -1) {                
                if (c == '\n') {
                    break;
                }                
                buf[cnt++] = (byte) c;                
            }            
            return new String(buf, 0, cnt);            
        }        
        
        public int nextInt() throws IOException {            
            int ret = 0;            
            byte c = read();            
            while (c <= ' ') {
                c = read();
            }            
            boolean neg = (c == '-');            
            if (neg) {
                c = read();
            }            
            do {                
                ret = ret * 10 + c - '0';                
            } while ((c = read()) >= '0' && c <= '9');            
            
            if (neg) {
                return -ret;
            }            
            return ret;            
        }        
        
        public long nextLong() throws IOException {            
            long ret = 0;            
            byte c = read();            
            while (c <= ' ') {
                c = read();
            }            
            boolean neg = (c == '-');            
            if (neg) {
                c = read();
            }            
            do {                
                ret = ret * 10 + c - '0';                
            } while ((c = read()) >= '0' && c <= '9');            
            if (neg) {
                return -ret;
            }            
            return ret;            
        }        
        
        public double nextDouble() throws IOException {            
            double ret = 0, div = 1;            
            byte c = read();            
            while (c <= ' ') {
                c = read();
            }            
            boolean neg = (c == '-');            
            if (neg) {
                c = read();
            }            
            
            do {                
                ret = ret * 10 + c - '0';                
            } while ((c = read()) >= '0' && c <= '9');            
            
            if (c == '.') {                
                while ((c = read()) >= '0' && c <= '9') {                    
                    ret += (c - '0') / (div *= 10);                    
                }                
            }            
            
            if (neg) {
                return -ret;
            }            
            return ret;            
        }        
        
        private void fillBuffer() throws IOException {            
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);            
            if (bytesRead == -1) {
                buffer[0] = -1;
            }            
        }        
        
        private byte read() throws IOException {            
            if (bufferPointer == bytesRead) {
                fillBuffer();
            }            
            return buffer[bufferPointer++];            
        }        
        
        public void close() throws IOException {            
            if (din == null) {
                return;
            }            
            din.close();            
        }        
    }    
}
