310692: CF1872A. Two Vessels

A. Two Vesselstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have two vessels with water. The first vessel contains $a$ grams of water, and the second vessel contains $b$ grams of water. Both vessels are very large and can hold any amount of water.

You also have an empty cup that can hold up to $c$ grams of water.

In one move, you can scoop up to $c$ grams of water from any vessel and pour it into the other vessel. Note that the mass of water poured in one move does not have to be an integer.

What is the minimum number of moves required to make the masses of water in the vessels equal? Note that you cannot perform any actions other than the described moves.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

Each test case consists of a single line containing three integers $a$, $b$, and $c$ ($1 \le a, b, c \le 100$) — the mass of water in the vessels and the capacity of the cup, respectively.

Output

For each test case, output a single number — the minimum number of moves required to make the masses of water in the vessels equal. It can be shown, that it is always possible.

ExampleInput

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

Output

1
3
0
1
50
16

Note

In the first test case, only one move is enough: if we pour $2$ grams of water from the second vessel into the first one, both vessels will contain $5$ grams of water.

In the second example test case, three moves are enough:

• Pour $3$ grams of water from the first vessel into the second one. After this move, the first vessel will contain $17 - 3 = 14$ grams of water, and the second vessel will contain $4 + 3 = 7$ grams.
• Pour $2$ grams of water from the first vessel into the second one. After this move, the first vessel will contain $14 - 2 = 12$ grams of water, and the second vessel will contain $7 + 2 = 9$ grams.
• Finally, pour $1.5$ grams of water from the first vessel into the second one. After this move, the first vessel will contain $12 - 1.5 = 10.5$ grams of water, and the second vessel will contain $9 + 1.5 = 10.5$ grams.

Note that this is not the only way to equalize the vessels in $3$ moves, but there is no way to do it in $2$ moves.

In the third example test case, the vessels initially contain the same amount of water, so no moves are needed. The answer is $0$.

题目大意：
你有两个装水的容器。第一个容器里有a克水，第二个容器里有b克水。两个容器都非常大，可以容纳任意量的水。

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

每次操作，你可以从任一容器中舀起最多c克水，然后倒入另一个容器中。注意，一次操作中倒入的水的质量不一定是整数。

问：使两个容器中的水质量相等所需的最小操作次数是多少？注意，你不能执行除了上述操作以外的任何动作。

输入输出数据格式：
输入：
每个测试包含多个测试案例。第一行包含测试案例的数量t（1≤t≤1000）。接下来是测试案例的描述。

每个测试案例由一行组成，包含三个整数a、b和c（1≤a,b,c≤100）——分别是容器中的水的质量和杯子的容量。

输出：
对于每个测试案例，输出一个数字——使容器中的水质量相等所需的最小操作次数。可以证明，这总是可能的。题目大意： 你有两个装水的容器。第一个容器里有a克水，第二个容器里有b克水。两个容器都非常大，可以容纳任意量的水。 你还有一个空杯子，最多可以装c克水。 每次操作，你可以从任一容器中舀起最多c克水，然后倒入另一个容器中。注意，一次操作中倒入的水的质量不一定是整数。 问：使两个容器中的水质量相等所需的最小操作次数是多少？注意，你不能执行除了上述操作以外的任何动作。 输入输出数据格式： 输入： 每个测试包含多个测试案例。第一行包含测试案例的数量t（1≤t≤1000）。接下来是测试案例的描述。 每个测试案例由一行组成，包含三个整数a、b和c（1≤a,b,c≤100）——分别是容器中的水的质量和杯子的容量。 输出： 对于每个测试案例，输出一个数字——使容器中的水质量相等所需的最小操作次数。可以证明，这总是可能的。