Codeforces Global Round 8

A. C+=

时间限制： 2 秒 内存限制： 512 MB

Leo 发明了一种新的编程语言 ​C+=。在 C+= 语言中，整数变量只能通过 += 操作来改变，它的作用是将右边的值加到左边的变量上。

例如，如果 a = 2, b = 3，执行 "a += b" 后，a 的值会变成 5，而 b 的值不变。

在一个原型程序中，Leo 有两个整数变量 a 和 b，它们一开始有一些正整数值。他可以执行任意多次 "a += b" 或 "b += a" 操作。

Leo 想测试大整数的处理，所以他希望使得 a 或 b 的值严格大于给定的整数 n。他想知道：最少需要多少次操作？

输入

• 第一行包含一个整数 $(T) ((1 \leq T \leq 100))$，表示测试用例数量。
• 接下来的$(T) 行中，每行包含三个整数$(a, b, n) $((1 \leq a, b \leq n \leq 10^9))$—— 初始的两个变量，以及需要超过的值 (n)。

输出

对于每个测试用例，输出一个整数 —— 达成目标所需的最少操作次数。每个答案占一行。

示例

输入

2
1 2 3
5 4 100

输出

2
7

说明

• 在第一个样例中，不可能只用一次操作就让某个变量大于 3。 一种方法是执行两次 "b += a"：
  • 第一次：b = 2 + 1 = 3
  • 第二次：b = 3 + 1 = 4 > 3 共 2 次操作。
• 在第二个样例中，经过 7 次操作可以让其中一个数超过 100。