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$$$) - a 和 b 的初始值,以及其中一个变量必须分别超过的值。
输出
对于每个测试用例,打印一个整数 - 所需的最小操作数。用换行符分隔答案。
示例
输入 #1
2 1 2 3 5 4 100
输出 #1
2 7
注意
在第一种情况下,我们不能在一次操作中使变量超过 $$$3$$$。通过两次操作实现此目的的一种方法是执行“b += a”两次。