题目描述

“动物森友会”是一款自由度很高的游戏，可以在自己的无人岛上建房子、种花种树，还能钓鲈鱼。

如果一个 $(2k-1)\times(2k-1)$ 的正方形土地满足最外圈的高度是 1，第二圈的高度是 2……以此类推，它就是一个高度为 k 的金字塔。下图是高度为 1 到 4 的金字塔的示例：

小 A 的岛大小是 $n\times m$ 的矩形，每个位置的高度都是已知的。他想要建造一个大大的金字塔。他拥有最多 $k$ 次改造地形机会，每次可以选择一个坐标，将这个点的高度增加 1，但是不能减少高度。请问，他能完成的金字塔的最高高度是多少？

输入格式

每个测试点由多组数据组成。

第一行为一个整数 $T$，代表数据的组数。

对于每组数据，第一行是三个整数 $n,m,k$，表示岛的大小和操作次数上限。接下来是个 $n$ 行 $m$ 列的矩阵，表示最开始的高度，每个数字之间用空格分隔。

输出格式

输出 $T$ 行，对于每行，都输出一个整数，表示每组数据下可以完成金字塔的最大高度。

3
5 5 10
1 1 1 1 1
1 2 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1
5 5 5
1 1 1 1 1
1 2 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1
1 1 1000000000
2

3
2
0

提示

对于所有测试数据，$1\le T \le 5$，$1 \le n,m \le 350$，$1\le k \le 10^8$，初始高度 0 到 50 的非负整数。