题目描述

青蛙 Freya 正在二维坐标平面上旅行。她目前位于点 $(0,0)$，想要到达点 $(x,y)$。每次移动时，她可以选择一个整数 $d$，满足 $0 \leq d \leq k$，并朝她面朝的方向前进 $d$ 个单位。

最开始，她面朝正 $x$ 轴方向。每次移动后，她会在正 $x$ 轴方向和正 $y$ 轴方向之间交替转向（也就是说，第二次移动时她会面朝正 $y$ 轴方向，第三次又面朝正 $x$ 轴方向，以此类推）。

她最少需要多少次移动，才能恰好到达点 $(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$）。

输出格式

对于每个测试用例，输出 Freya 到达目标点所需的最少跳跃次数，每个答案占一行。

样例

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

由 ChatGPT 4.1 翻译

来源

Codeforces 2009C，英文题名 The Legend of Freya the Frog。