← 返回题目列表

Codeforces · 1368/A

A. C加加

中文机器翻译题面 查看原题

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”两次。