问题描述

青蛙 $Freya$ 正在二维坐标平面上移动。她当前位于点 $(0,0)$，想要到达点 $(x,y)$。在一次移动中，她可以选择一个整数 $d$，其中 $0 ≤ d ≤ k$，并朝着她面向的方向跳 $d$ 个单位。

最开始，她面朝正 $x$ 方向。每次跳跃后，她会在正 $x$ 方向和正 $y$ 方向之间交替转向（即，她在第二次跳跃时会面向正 $y$ 方向，第三次跳跃面向正 $x$ 方向，以此类推）。

求她最少需要跳多少次才能到达点 $(x,y)。$

输入格式

第一行包含一个整数 $t$ $(1 ≤ t ≤ 10^4)$，表示测试用例的数量。

每个测试用例包含三个整数 $x, y$ 和 $k$ $(0 ≤ x, y ≤ 10^9, 1 ≤ k ≤ 10^9)。$

输出格式

对于每个测试用例，输出 $Freya$ 需要跳跃的最少次数，每个结果占一行。

输入样例：

3
9 11 3
0 10 8
1000000 100000 10

输出样例：

8
4
199999