题目描述

蟾蜍女士正在二维坐标平面上旅行。她目前在点 $(0,0)$，目标是到达点 $(x,y)$。每一步中，她可以选择一个整数 $d$（满足 $0 \le d \le k$），并在她当前面向的方向上跳跃 $d$ 个单位。

起初，她面向正 $x$ 轴方向。每次跳跃后，她会交替改变方向：第一次跳跃后仍面向正 $x$ 轴，第二次跳跃时改为面向正 $y$ 轴，第三次跳跃又转回正 $x$ 轴，以此类推。

请问，蟾蜍女士至少需要进行多少次跳跃才能刚好落在点 $(x,y)$？

输入格式

第一行包含一个整数 $t$，表示测试组数，$1 \le t \le 10^4$。

接下来每个测试组一行，包含三个整数 $x$、$y$ 和 $k$，满足

$0 \le x, y \le 10^9,\quad 1 \le k \le 10^9.$

输出格式

对于每个测试组，输出一行一个整数，表示蟾蜍女士至少需要的跳跃次数。

样例输入

3
9 11 3
0 10 8
1000000 100000 10

样例输出

8
4
199999

说明

在第一个样例中，一组最优的跳跃序列为： $(0,0) \to (2,0) \to (2,2) \to (3,2) \to (3,5) \to (6,5) \to (6,8) \to (9,8) \to (9,11)$，共 $8$ 次跳跃。