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.lang.*;
	import java.math.*;
	import java.text.*;
	import java.io.*;
	
	public final class Solution {
		static PrintWriter out = new PrintWriter(System.out); 
		 static void flush() {
	 		out.flush();
	 	}
		static class FastReader {
	        BufferedReader br;
	        StringTokenizer st;
	
	        public FastReader() {
	            br = new BufferedReader(new
	                    InputStreamReader(System.in));
	        }
	        static boolean isPalindrome(String str1, String str2) {
	    		String str3 = str1+str2;
	    		int i = 0;
	    		int j = str3.length()-1;
	    		while(i < j) {
	    			char a = str3.charAt(i);
	    			char b = str3.charAt(j);
	    			if(a != b) return false;
	    			i++;
	    			j--;
	    		}
	    		return true;
	    	}
	    	static boolean isPalindrome(String str) {
	    		int i = 0;
	    		int j = str.length()-1;
	    		while(i < j) {
	    			char a = str.charAt(i);
	    			char b = str.charAt(j);
	    			if(a != b) return false;
	    			i++;
	    			j--;
	    		}
	    		return true;
	    	}
	        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());
	        }
	        static int fact(int n) {
	   		 if(n == 1) return 1;
	   		 return n * fact(n-1);
	   	 }
		public int[] readIntArray(int n) {
				int[] arr = new int[n];
				for(int i=0; i<n; ++i)
					arr[i]=nextInt();
				return arr;
			}
		public String[] readStringArray(int n) {
			String[] arr = new String[n];
			for(int i=0; i<n; ++i)
				arr[i]= nextLine();
			return arr;
		}
			static int gcd(int a, int b) { 
		    if (b == 0) return a; 
		    return gcd(b, a % b);  
			}
	        double nextDouble() {
	            return Double.parseDouble(next());
	        }
	        String nextLine() {
	            String str = "";
	            try{
	                str = br.readLine();
	            }
	            catch (IOException e) {
	                e.printStackTrace();
	            }
	            return str;
	        }
	    }
		
		 static long solve(long a, long b, long n) {
			long x = Math.max(a, b);
			long y = Math.min(a, b);
			 long count = 0;
			 while(true) {
				 y += x;
				 count++;
				 if(y > n) {
					 return count;
				 }
				 x += y;
				 	count++;
				 if(x > n) {
					 return count;
				 }
			 }
		 }
		public static void main(String args[]) throws Exception {
	        FastReader sc = new FastReader();
	        long start = System.currentTimeMillis();
	        int t = sc.nextInt();
	        
	        while(t-- > 0) {
	        	long a = sc.nextLong();
	        	long b = sc.nextLong();
	        	long n = sc.nextLong();
	        	
	        	out.println(solve(a,b,n));
	        }
	        	flush();
	        	long end = System.currentTimeMillis();
	        	NumberFormat formatter = new DecimalFormat("#0.00000");
	        	//System.out.print("Execution time is " + formatter.format((end - start) / 1000d) + " seconds");
	        }
	}
