测试数据来自 system/1915

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　侦察小分队要从一个 \(m×n\) 的网格的左上角\(（1，1）\)走到右下角\(（m，n）\)去执行任务。网格中的一些格子是空地，用 0 表示，其它格子是障碍，用 1 表示。机器人每次可以往上、下、左、右四个方向走一格，但不能连续地穿越 \(k\) 个障碍，求最短路长度。起点和终点保证是空地。起点和终点保证是空地。

【输入格式】

　　第一行一个整数 \(T\)，表示测试数据组数。
　　每组数据的第一行为 \(m,n,k\)，表示网格的行列数，接下来的 \(m\) 行，每行含 \(n\) 个数字，数字 0 表示空地，1 表示障碍。

【输出格式】

　　每组数据输出一行，表示最短路长度，如果无解则输出 -1。

【输入输出样例】

　Input

3
2 5 0
0 1 0 0 0
0 0 0 1 0
4 6 1
0 1 1 0 0 0
0 0 1 0 1 1
0 1 1 1 1 0
0 1 1 1 0 0
2 2 0
0 1
1 0

　Output

7
10
-1

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤m,n,k≤20\)。

【来源】

　　Mr.he