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

public class New_lang {
	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[1000000]; // 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(); 
	    } 
	}

	public static void main(String[] args)throws IOException{
		// TODO Auto-generated method stub
		Reader sc=new Reader();
		PrintWriter pw=new PrintWriter(System.out);
		int t=sc.nextInt();
		for(int i=0;i<t;i++) {
			long a=sc.nextInt();
			long b=sc.nextInt();
			long n=sc.nextInt();
			
			int c=0;
			if(a<=b) {
				while(a<=n && b<=n) {
					
					a+=b;
					c++;
					if(a>n) {
						break;
					}
					b+=a;
					c++;
					if(b>n) {
						break;
					}
				}
			}
			else {
				while(b<=n && a<=n) {
					b+=a;
					c++;
					if(b>n) {
						break;
					}
					a+=b;
					c++;
					if(a>n) {
						break;
					}
				}
			}
			pw.println(c);
		}
		pw.flush();
		

	}

}
