На бесконечном клетчатом поле в клетке $$$(a,b)$$$ стоит робот. Миша хочет привести его в клетку $$$(0,0)$$$. Для этого он зафиксировал некоторое целое число $$$k$$$.
Миша может выполнять следующую операцию: выбрать два целых числа $$$dx$$$ и $$$dy$$$ (оба от $$$0$$$ до $$$k$$$ включительно) и передвинуть робота на $$$dx$$$ клеток влево (по направлению уменьшения $$$x$$$ координаты) и на $$$dy$$$ клеток вниз (по направлению уменьшения $$$y$$$ координаты). Другими словами, переместить робота из клетки $$$(x,y)$$$ в $$$(x - dx, y - dy)$$$.
Стоимость операции равна:
Обратите внимание, что если $$$dx \ne dy$$$, пары $$$(dx, dy)$$$ и $$$(dy, dx)$$$ являются различными.
Помогите Мише привести робота в клетку $$$(0,0)$$$ за минимальную суммарную стоимость. Обратите внимание, что минимизировать количество операций не требуется.
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В единственной строке каждого набора входных данных записаны три целых числа $$$a, b$$$ и $$$k$$$ ($$$1 \le a, b, k \le 10^{18}$$$).
На каждый набор входных данных выведите одно целое число — минимальная суммарная стоимость операций, необходимых для перемещения робота в клетку $$$(0,0)$$$.
43 5 152 3 112 18 89 7 5
1 2 1 2
В первом наборе входных данных можно один раз применить операцию $$$(3,5)$$$. Робот сразу окажется в $$$(0,0)$$$, стоимость операции будет равна $$$1$$$.
Во втором наборе можно применить операции: $$$(1,1)$$$, $$$(0,1)$$$ и $$$(1,1)$$$. После первой операции робот окажется в клетке $$$(1,2)$$$, после второй — в $$$(1,1)$$$, после третьей — в $$$(0,0)$$$. Стоимость первой и второй операций равна $$$1$$$, а третьей — $$$0$$$, так как пара $$$(1,1)$$$ уже использовалась в первой операции.
В третьем наборе можно три раза подряд выбрать пару $$$(4,6)$$$.
В четвертом наборе можно применить операции: $$$(4,2)$$$ и $$$(5,5)$$$.
