3072: Bamboo Rat

In recent time, Hua Nong brothers' bamboo rat videos go viral and they have been Internet celebrities ever since then. As an investor, Boss Niu decides to build a breeding base to culture bamboo rats. The breeding base can be described as a $n\times m$ matrix, each cell of which contains a bamboo rat. Generally, every bamboo rat has a weight $w$.

Today, Brother Wang comes to visit Boss Niu. Thus Boss Niu will select exactly k pretty bamboo rats to roast. In order not to make breeding base look so empty, Boss Niu can't select two adjacent bamboo rats. That is to say, if there are two bamboo rats sharing the same edge, he just can select one at most.

Among k bamboo rats he selects, Boss Niu wants the weight of the lightest bamboo rat maximum. Please tell him the maximum weight of the lightest one.

The first line contains an integer number T, the number of test cases.

For each test case :

The first line contains three integers $n$, $m$, $k$($1 \leq n\times m \leq 1000, 1 \leq k \leq (n\times m+1)/2$), the size of matrix and the number Boss Niu need select.

The following $n$ lines, each contains $m$ integers $w_{i,j}$($1 \leq w_{i,j} \leq 1000$), the weight of bamboo rats.

For each test case print the answer.

2
2 2 2
4 3
3 2
3 3 4
3 7 8
4 9 6
7 4 2

3
4