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