B. Влево и вниз
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На бесконечном клетчатом поле в клетке $$$(a,b)$$$ стоит робот. Миша хочет привести его в клетку $$$(0,0)$$$. Для этого он зафиксировал некоторое целое число $$$k$$$.

Миша может выполнять следующую операцию: выбрать два целых числа $$$dx$$$ и $$$dy$$$ (оба от $$$0$$$ до $$$k$$$ включительно) и передвинуть робота на $$$dx$$$ клеток влево (по направлению уменьшения $$$x$$$ координаты) и на $$$dy$$$ клеток вниз (по направлению уменьшения $$$y$$$ координаты). Другими словами, переместить робота из клетки $$$(x,y)$$$ в $$$(x - dx, y - dy)$$$.

Стоимость операции равна:

  • $$$1$$$, если выбранная пара $$$(dx,dy)$$$ используется впервые;
  • $$$0$$$, если пара $$$(dx,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)$$$.

Пример
Входные данные
4
3 5 15
2 3 1
12 18 8
9 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)$$$.