该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：1 Sec 内存限制：256 MB 输入文件：frog.in 输出文件：frog.out

小明养了一只青蛙，天天训练它跳方格。

小明将青蛙放在平面直角坐标系的原点，然后他会设置一个目的地坐标 $(x,y)$，并规定一个最大步数 $k$。

青蛙每次在跳跃之前，先选择一个距离 $d$（$0 \le d \le k$），然后跳跃距离 $d$。

青蛙第一次跳跃是面向X轴正向跳的，然后面向Y轴正向跳跃，再面向X轴正向跳跃，再面向Y轴正向跳跃，依次类推，每一次跳跃都转变一次方向，直到跳到目的地为止。

请你计算青蛙至少需要跳跃多少次。

输入格式

第一行为一个整数 $t$，表示有 $t$ 组询问；

接下来有 $t$ 行，第 $i$ 行为第 $i$ 组询问，每行包含空格分隔的三个整数 $x$、$y$、$k$。

输出格式

$t$ 行，第 $i$ 行为对第 $i$ 组询问的回答。

样例

样例 1

3
9 11 3
0 10 8
1000000 1000000 10

8
4
200000

样例说明：

在第 $1$ 组询问里，青蛙按如下顺序跳跃：

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

共跳跃了 $8$ 次。可以证明没有更少步数的跳法了。

数据范围

$1 \le t \le 10^4$

$0 \le x,y \le 10^9$

$1 \le k \le 10^9$