题目描述

翁老师来到了一个二维平面，即将开始他的旅行。

他初始在位置 $(0,0)$，想去点 $(x,y)$。在每次跳跃时，他可以选择一个整数 $d$，使得 $0\leq d\leq k$。然后进行一次跳跃，跳跃只能是以下两种方式：

• 操作一：沿着 $x$ 轴正方向跳跃，具体来说目前在 $(x,y)$，下次跳跃到 $(x+d,y)$
• 操作二：沿着 $y$ 轴正方向跳跃，具体来说目前在 $(x,y)$，下次跳跃到 $(x,y+d)$

若选择 $d=0$，则当前位置不变。

跳跃必须用以上两个操作交替进行，具体来说如下：

• 翁老师必须交替使用两种操作：第一次使用操作一，第二次使用操作二，如此交替进行。

请问翁老师最少几步可以跳到终点 $(x,y)$

输入格式

本题有多组数据

第一行输入一个正整数 $t$ 表示测试数据组数。每一组数据：

• 输入三个空格隔开的正整数 $x,y,k$。

输出格式

输出一共输出 $t$ 行，每行一个整数代表最小步数。

3
9 11 3
0 10 8
1000000 100000 10

8
4
199999

样例 1 解释

在第一个例子中，可以按如下路径跳跃：

$$(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$ 次跳跃。

样例 2

见下发文件

数据范围

• $20\%$ 的数据满足，$t=1$，$0\leq x,y\leq 10$，$10\leq k\leq 100$
• 另外 $20\%$ 的数据满足 $1\leq t\leq 100$，$0\leq x,y\leq 100$，$k=1$。
• $60\%$ 的数据满足，$1\leq t\leq 100$，$0\leq x,y\leq 100$，$1\leq k\leq 100$
• $100\%$ 的数据满足，$1\leq t\leq 10^4$，$0\leq x,y\leq 10^9$，$1\leq k\leq 10^9$