Mr. Conical 是一位狂热的谜题游戏爱好者，热衷于解决各种谜题。一天，当他醒来时，发现自己置身于一个拥有 $n$ 行 $m$ 列的网格状迷宫中。在这个迷宫中，某些格子是障碍物，而其他格子上则有一定数量的金币。第 $i$ 行第 $j$ 列的格子包含 $a_{i,j}$ 个金币。在每一步中，Mr. Conical 只能从当前所在的格子移动到与其上、下、左、右相邻且非障碍的格子。

当 Mr. Conical 从另一个格子移动到特定格子 $(i, j)$ 时，他可以获得 $a_{i,j}$ 个金币。请注意，金币不会消失，这意味着下一次他再次到达 $(i, j)$ 时，他将再次获得 $a_{i,j}$ 个金币。Mr. Conical 目前位于 $(1, 1)$ 且没有金币。为了逃离迷宫，他必须前往 $(n, m)$。然而，在 $(n, m)$ 处有一名守卫，必须给守卫 $K$ 个金币才能离开迷宫。

Mr. Conical 是一位热衷于解谜的人，但他缺乏耐心，因此他想知道自己逃离迷宫所需的最少步数。

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 5$)，表示测试用例的数量。

接下来是 $T$ 个测试用例的描述。

对于每个测试用例，第一行包含三个整数 $n, m, K$ —— 分别表示网格状迷宫的行数和列数，以及必须给守卫的金币数量。保证 $n \times m \le 4000$ 且 $K \le 10^9$。

接下来的 $n$ 行描述了整个迷宫。每行包含 $m$ 个整数 $a_{i,j}$ ($-1 \le a_{i,j} \le 10^9$)。如果 $a_{i,j} = -1$，则表示 $(i, j)$ 是障碍物。否则，表示 $(i, j)$ 上有 $a_{i,j}$ 个金币。

输出格式

对于每个测试用例，在单独的一行中输出一个数字表示答案。

样例

输入样例 1

2
3 3 10
0 -1 4
1 2 1
5 -1 0
4 4 1
2 0 -1 0
0 -1 0 -1
-1 7 3 3
1 2 3 0

输出样例 1

6
-1