C. Легенда о лягушке Лее
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лягушка Лея путешествует по двумерной координатной плоскости. В данный момент она находится в точке $$$(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$$$).

Выходные данные

Для каждого набора входных данных выведите количество прыжков, которые необходимо сделать Лее, в отдельной строке.

Пример
Входные данные
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 прыжков.