Problem Description

度度熊喜欢旅行，也喜欢这句话——“这美丽世界已经拥有你，我已经拥有这美丽世界。”

度度熊有一个$n \times m$的棋盘，第$i$行第$j$列的格子颜色为$A_{i,j}$。特别的，当$A_{i,j}=0$,这个点是**无色**的；当$A_{i,j}=-1$时，该格子是**障碍点**，不能被遍历。

度度熊可以选择棋盘上任何一点作为起点，每过一个时刻，度度熊可以走到相邻上下左右的某个格子。假设度度熊在$(x,y)$，则他可以走到$(x-1,y),(x+1,y),(x,y-1),(x,y+1)$中某一个格子，但不能出界。**度度熊可以遍历到已经走过的格子**，并可以在任何一点结束他的旅行。

度度熊把遍历到的所有**有颜色（即$A_{i,j} > 0$）**的格子的颜色拿出来，其中不同颜色个数就是本次行走的**带劲值**。

给定K，问带劲值 **大于等于** K的，耗时最短的行走，时间为多少。
**如果无解，则输出-1**。

Input

第一行一个数，表示数据组数$T$。

每组数据第一行三个数$n,m,K$；接下来$n$行，每行$m$个数，第$i$行第$j$个元素为$A_{i,j}$。

数据组数T=21，满足：

- $1 \le n,m \le 20$
- $1 \le K \le 7$
- $-1 \le A_{i,j} \le nm$

其中10组数据满足$n,m \le 10$。

Output

每组数据输出一行，每行仅包含一个数，表示带劲值大于等于K的，耗时最短的行走，时间为多少。

3
3 3 3
2 1 3 
5 2 2 
3 1 3 
3 3 3
0 -1 1 
-1 1 3 
5 -1 0 
3 3 3
2 5 4 
3 2 3 
0 5 1 

2
-1
2