← 返回题目列表

Codeforces · 2009/C

C. 青蛙芙蕾雅的传奇

中文机器翻译题面 查看原题

青蛙 Freya 正在 2D 坐标平面上移动。她当前位于点 $$$(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 需要在新行上进行的跳转次数。

示例

输入 #1

3
9 11 3
0 10 8
1000000 100000 10

输出 #1

8
4
199999

注意

在第一个示例中,一组最佳移动是 Freya 按以下方式跳跃: ($$$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 次跳跃。