H. Странная матрица
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана матрица $$$a$$$ размера $$$n \times m$$$, состоящая из целых чисел от $$$0$$$ до $$$31$$$ включительно.

Назовем матрицу странной, если для любых ее двух различных строк $$$i$$$ и $$$j$$$ выполняются оба следующих условия:

  • для каждого набора из $$$k$$$ индексов $$$(x_1, x_2, \dots, x_k)$$$, где $$$1 \le x_1 < x_2 < \cdots < x_k \le m$$$, выполняется равенство $$$a_{i, x_1} \mathbin{\&} a_{j, x_1} \mathbin{\&} a_{i, x_2} \mathbin{\&} a_{j, x_2} \mathbin{\&} \cdots \mathbin{\&} a_{i, x_k} \mathbin{\&} a_{j, x_k} = 0$$$ (где $$$\mathbin{\&}$$$ — побитовое И двух чисел);
  • для каждого набора из $$$k$$$ индексов $$$(x_1, x_2, \dots, x_k)$$$, где $$$1 \le x_1 < x_2 < \cdots < x_k \le m$$$, выполняется равенство $$$a_{i, x_1} \mathbin{|} a_{j, x_1} \mathbin{|} a_{i, x_2} \mathbin{|} a_{j, x_2} \mathbin{|} \cdots \mathbin{|} a_{i, x_k} \mathbin{|} a_{j, x_k} = 31$$$ (где $$$\mathbin{|}$$$ — побитовое ИЛИ двух чисел).

Вы можете выполнять следующее действие любое количество раз: взять любую строку матрицы и число $$$y$$$ от $$$0$$$ до $$$31$$$ включительно; а затем применить побитовое исключающее ИЛИ (XOR) с числом $$$y$$$ ко всем элементам выбранной строки. Стоимость такой операции равна $$$y$$$.

Ваша задача — определить минимальную стоимость, чтобы сделать матрицу странной. Или сообщите, что это невозможно.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

Первая строка каждого набора содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n, m \le 50$$$; $$$1 \le k \le m$$$).

Далее следует $$$n$$$ строк, $$$i$$$-я из них содержит по $$$m$$$ целых чисел $$$a_{i, 1}, a_{i, 2}, \dots, a_{i, m}$$$ ($$$0 \le a_{i, j} \le 31$$$).

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

Для каждого набора входных данных выведите одно целое число — минимальную стоимость, чтобы сделать матрицу странной; или -1, если матрицу невозможно сделать странной.

Пример
Входные данные
3
2 3 1
0 1 0
1 0 1
3 2 2
0 1
2 3
4 5
5 5 5
0 5 17 4 22
8 5 16 21 9
7 25 31 30 8
0 0 5 15 13
1 2 3 4 5
Выходные данные
30
-1
24