题目描述

你有两个盛水的水桶。第一个水桶装有 a 克水，第二个水桶装有 b 克水。两个水桶都非常大，可以容纳任何数量的水。

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

在一次移动中，你可以从任意一个水桶中舀取 最多 c 克水，倒入另一个水桶中。注意，一次移动中倒出的水量不必是整数。

你的目标是让两个水桶中的水量相等。请计算达到这个目标所需的最少移动次数。
注意：除了所描述的移动之外，不能执行其他操作。

可以证明，在任意合法输入下，始终可以达成目标。

输入格式

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

输出格式

对于每个测试用例，输出一个整数，表示使两个水桶中水量相等所需的最小移动次数。

输入样例 #1

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

输出样例 #1

1  
3  
0  
1  
50  
16

题目说明

在第一个测试案例中，只需要移动一次就足够了：如果我们从第二个水桶中倒入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克。