题目描述

你有两个装有水的容器。第一个容器中有 $a$ 克水，第二个容器中有 $b$ 克水。两个容器都非常大，可以容纳任意多的水。

你还有一个空杯子，最多可以装 $c$ 克水。

每次操作，你可以从任意一个容器中舀出不超过 $c$ 克的水，并倒入另一个容器。注意，每次倒入的水的质量不一定是整数。

你需要做的，是使两个容器中的水的质量相等。请问最少需要多少次操作？注意，你不能进行题目描述以外的其他操作。

输入格式

每组测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。接下来的每组测试用例，每组一行，包含三个整数 $a$、$b$ 和 $c$（$1 \le a, b, c \le 100$），分别表示两个容器中的水的质量和杯子的容量。

输出格式

对于每个测试用例，输出一个整数，表示使两个容器中的水的质量相等所需的最少操作次数。可以保证一定有解。

说明/提示

在第一个测试用例中，只需一次操作：如果我们从第二个容器向第一个容器倒入 $2$ 克水，两个容器中都会有 $5$ 克水。

在第二个测试用例中，三次操作即可：

• 从第一个容器向第二个容器倒入 $3$ 克水。此时，第一个容器剩下 $17-3=14$ 克水，第二个容器有 $4+3=7$ 克水。
• 再从第一个容器向第二个容器倒入 $2$ 克水。此时，第一个容器剩下 $14-2=12$ 克水，第二个容器有 $7+2=9$ 克水。
• 最后从第一个容器向第二个容器倒入 $1.5$ 克水。此时，第一个容器剩下 $12-1.5=10.5$ 克水，第二个容器有 $9+1.5=10.5$ 克水。

注意，这不是唯一的三步方案，但无法在两步内完成。

在第三个测试用例中，两个容器初始时水量相等，因此不需要任何操作，答案为 $0$。

由 ChatGPT 4.1 翻译

样例

6
3 7 2
17 4 3
17 17 1
17 21 100
1 100 1
97 4 3

1
3
0
1
50
16