Вы получили сетку размером \(n\times m\) от таинственного источника. Источник также дал вам волшебную целую положительную константу \(k\).
Источник сказал вам покрасить сетку некоторыми цветами, удовлетворяя следующее условие:
Вам не нравится использовать слишком много цветов. Пожалуйста, найдите минимальное количество цветов, необходимое для раскрашивания сетки.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число \(t\) (\(1\le t\le1000\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит три целых числа \(n\), \(m\), \(k\) (\(1\le n,m,k\le10^4\)) — размеры сетки и магическая константа.
Для каждого набора входных данных выведите одно целое число — минимальное количество цветов, необходимое, чтобы покрасить сетку.
В первом наборе входных данных одной из оптимальных конструкций является:
Во втором наборе входных данных цвета всех ячеек должны быть попарно различными, поэтому ответ — \(5\).
6 3 3 2 5 1 10000 7 3 4 3 2 7 8 9 6 2 5 4
4 5 12 6 36 8
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач