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 javax.print.attribute.IntegerSyntax;

import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;

public class Main {

	static boolean[] primecheck = new boolean[1000002];
	static ArrayList<Long> lucky = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		OutputStream outputStream = System.out;
		FastReader in = new FastReader();
		PrintWriter out = new PrintWriter(outputStream);
		PROBLEM solver = new PROBLEM();
                 int  t = in.nextInt();
                 while(t-->0) {
					 solver.solve(in, out);
				 }
		  out.close();
	}

	public static void luckIsCalling(long n){

		long a = n*10 + 4;
		long b = n*10 + 7;

		lucky.add(a);
		lucky.add(b);

		if(a<=4444444444L) luckIsCalling(a);
		if(b<=4444444444L) luckIsCalling(b);
	}

	static class PROBLEM {

		public void solve(FastReader in, PrintWriter out) {
			long a = in.nextLong();
			long b = in.nextLong();
			 long n = in.nextLong();
			 long ans=0;
			 while(true)
			 {
				 if(a>n||b>n)
				 {
					 break;
				 }
			 	if((a+b)>n)
				{
					ans++;
					break;
				}
			 	if(a>b)
				{
					if((a+2*b)>n)
					{
						a+=b;
						a+=b;
						ans+=2;

					}
					else
					{
						b+=a;
						a+=b;
						ans+=2;
					}
				}
			 	else
				{
					if((b+2*a)>n)
					{
						b+=a;
						b+=a;
						ans+=2;

					}
					else
					{
						a+=b;
						b+=a;
						ans+=2;
					}
				}

			 }
			 out.println(ans);
}
	}
		static boolean isPalindrome(char[] s) {
			int flag = 1;
			for (int i = 0; i < s.length; i++) {
				if (s[i] != s[s.length - 1 - i]) {
					flag = 0;
					break;
				}
			}
			if (flag == 1) return true;
			else return false;
		}

		static long gcd(long a, long b) {
			if (b == 0) return a;
			return gcd(b, a % b);
		}

		static boolean isSquare(double a) {
			boolean isSq = false;
			double b = Math.sqrt(a);
			double c = Math.sqrt(a) - Math.floor(b);

			if (c == 0) isSq = true;

			return isSq;
		}

		static int exponentMod(int A, int B, int C) {

			// Base cases
			if (A == 0)
				return 0;
			if (B == 0)
				return 1;

			// If B is even
			long y;
			if (B % 2 == 0) {
				y = exponentMod(A, B / 2, C);
				y = (y * y) % C;
			}

			// If B is odd
			else {
				y = A % C;
				y = (y * exponentMod(A, B - 1,
						C) % C) % C;
			}

			return (int) ((y + C) % C);
		}

		public static class Pair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<Pair<U, V>> {
			public U x;
			public V y;

			public Pair(U x, V y) {
				this.x = x;
				this.y = y;
			}

			public int hashCode() {
				return (x == null ? 0 : x.hashCode() * 31) + (y == null ? 0 : y.hashCode());
			}

			public boolean equals(Object o) {
				if (this == o)
					return true;
				if (o == null || getClass() != o.getClass())
					return false;
				Pair<U, V> p = (Pair<U, V>) o;
				return (x == null ? p.x == null : x.equals(p.x)) && (y == null ? p.y == null : y.equals(p.y));
			}

			public int compareTo(Pair<U, V> b) {
				int cmpU = x.compareTo(b.x);
				return cmpU != 0 ? cmpU : y.compareTo(b.y);
			}

			public String toString() {
				return String.format("(%s, %s)", x.toString(), y.toString());
			}

		}

		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());
			}

			char nextChar() {
				return next().charAt(0);
			}

			boolean nextBoolean() {
				return !(nextInt() == 0);
			}
			// boolean nextBoolean(){return Boolean.parseBoolean(next());}

			String nextLine() {
				String str = "";
				try {
					str = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				return str;
			}

			public int[] readArray(int size) {
				int[] array = new int[size];
				for (int i = 0; i < size; i++) array[i] = nextInt();
				return array;
			}

		}

		private static int[] mergeSort(int[] array) {

			if (array.length <= 1) {
				return array;
			}

			int midpoint = array.length / 2;

			int[] left = new int[midpoint];
			int[] right;

			if (array.length % 2 == 0) {
				right = new int[midpoint];
			} else {
				right = new int[midpoint + 1];
			}

			for (int i = 0; i < left.length; i++) {
				left[i] = array[i];
			}

			for (int i = 0; i < right.length; i++) {
				right[i] = array[i + midpoint];
			}

			int[] result = new int[array.length];

			left = mergeSort(left);
			right = mergeSort(right);

			result = merge(left, right);

			return result;
		}

		private static int[] merge(int[] left, int[] right) {

			int[] result = new int[left.length + right.length];
			int leftPointer = 0, rightPointer = 0, resultPointer = 0;

			while (leftPointer < left.length || rightPointer < right.length) {

				if (leftPointer < left.length && rightPointer < right.length) {

					if (left[leftPointer] < right[rightPointer]) {
						result[resultPointer++] = left[leftPointer++];
					} else {
						result[resultPointer++] = right[rightPointer++];
					}
				} else if (leftPointer < left.length) {
					result[resultPointer++] = left[leftPointer++];
				} else {
					result[resultPointer++] = right[rightPointer++];
				}
			}
			return result;
		}

		public static void Sieve(int n) {

			Arrays.fill(primecheck, true);
			primecheck[0] = false;
			primecheck[1] = false;

			for (int i = 2; i * i < n + 1; i++) {
				if (primecheck[i]) {
					for (int j = i * 2; j < n + 1; j += i) {
						primecheck[j] = false;
					}
				}
			}
		}

	}


