Вы получили сетку размером $$$n\times m$$$ от таинственного источника. Источник также дал вам волшебную целую положительную константу $$$k$$$.
Источник сказал вам покрасить сетку некоторыми цветами, удовлетворяя следующее условие:
- Если $$$(x_1,y_1)$$$, $$$(x_2,y_2)$$$ — это две различные клетки одинакового цвета, то $$$\max(|x_1-x_2|,|y_1-y_2|)\ge k$$$.
Вам не нравится использовать слишком много цветов. Пожалуйста, найдите минимальное количество цветов, необходимое для раскрашивания сетки.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1\le t\le1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$, $$$k$$$ ($$$1\le n,m,k\le10^4$$$) — размеры сетки и магическая константа.
Для каждого набора входных данных выведите одно целое число — минимальное количество цветов, необходимое, чтобы покрасить сетку.
63 3 25 1 100007 3 43 2 78 9 62 5 4
4 5 12 6 36 8
В первом наборе входных данных одной из оптимальных конструкций является:
Во втором наборе входных данных цвета всех ячеек должны быть попарно различными, поэтому ответ — $$$5$$$.
