题目描述

在一个神秘的二维世界中，小可是一位勇敢的冒险者。他目前位于点$(0, 0)$，并希望前往点$(x, y)$。在这个世界中，小可的移动方式非常独特：在一次移动中，他选择一个整数$d$，使得$0 \leq d \leq k$，并在他当前面对的方向上向前跳跃$d$个单位。

最初，小可面向右方向。每次移动后，他会根据一个神秘的规则改变方向：他会在右方向和上方向之间交替（即，他在第二次移动时面向上方向，在第三次移动时面向右方向，依此类推）。

问题: 小可必须执行的最少移动次数是多少才能到达点$(x, y)$？

输入格式:

• 第一行包含一个整数$t$（$1 \leq t \leq 10^4$）—— 测试用例的数量。
• 每个测试用例包含三个整数$x$、$y$和$k$（$0 \leq x, y \leq 10^9, 1 \leq k \leq 10^9$）。

输出格式:

• 对于每个测试用例，输出小可需要进行的跳跃次数，每个结果占一行。

3
9 11 3
0 10 8
1000000 100000 10

8
4
199999

样例解释

在第一个样例中，小可的一个最优移动序列如下：

$$(0, 0) \rightarrow (2, 0) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 5) \rightarrow (6, 5) \rightarrow (6, 8) \rightarrow (9, 8) \rightarrow (9, 11)$$

这需要8次跳跃。

数据范围

测试点	$T \leq$	$x,y \leq$	$k \leq$	特殊性质
$1\sim 2$	$1$	$10$		无
$3\sim5$	$5$	$10^6$
$7\sim 10$	$10^4$	$10^9$