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 \lt x_2 \lt \cdots \lt 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 \lt x_2 \lt \cdots \lt 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.

Input

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$$$).

Output

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.

Strange Matrix

Examples