CF2011H Strange Matrix

You are given a matrix $ a $ of size $ n \times m $ , consisting of integers from $ 0 $ to $ 31 $ inclusive. Let's call the matrix strange if for every two distinct rows $ i $ and $ j $ , both of the following conditions hold: - for every set of $ k $ indices $ (x_1, x_2, \dots, x_k) $ , where $ 1 \le x_1 < x_2 < \cdots < x_k \le m $ , the equality $ 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 $ holds (where $ \mathbin{\&} $ — bitwise AND of two numbers); - for every set of $ k $ indices $ (x_1, x_2, \dots, x_k) $ , where $ 1 \le x_1 < x_2 < \cdots < x_k \le m $ , the equality $ 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 $ holds (where $ \mathbin{|} $ — bitwise OR of two numbers). You can perform the following operation any number of times: take any row of the matrix and a number $ y $ from $ 0 $ to $ 31 $ inclusive; then apply the bitwise XOR with the number $ y $ to all elements of the selected row. The cost of such an operation is equal to $ y $ . Your task is to calculate the minimum cost to make the matrix strange, or report that it is impossible.

The first line contains one integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The first line of each test case contains three integers $ n $ , $ m $ , and $ k $ ( $ 1 \le n, m \le 50 $ ; $ 1 \le k \le m $ ). Next, there are $ n $ lines, the $ i $ -th of which contains $ m $ integers $ a_{i, 1}, a_{i, 2}, \dots, a_{i, m} $ ( $ 0 \le a_{i, j} \le 31 $ ).

For each test case, output one integer — the minimum cost to make the matrix strange, or -1 if it is impossible to make the matrix strange.