征服者 SLF 觉得 FS 占领的那座城市——君士坦丁堡的名字太难听了，所以决定要攻打君士坦丁堡并将其改名为伊斯坦布尔。SLF 首先要解决 FS 附近的海上优势，不然对君士坦丁堡的攻打会十分困难。SLF 想到了一个绝妙的主意：他要把大海上的舰队通过陆路拖到内海，来占据海上优势。可是旱地行舟可不是个简单的活，你能帮他找到最短的那条陆路吗？

SLF 已经把连接大海和内海的陆地抽象成一个拥有 N \times N 个格子的正方形，每个格子都有一个数字。在每个格子上可以上、下、左、右走，但不能走出边界。从起点的格子走到终点的格子的路上所经过的格子的数字的总和则是这一路上的路程。求最小的路程。

先输入一个整数 T \ (1 \leq T \leq 10)，代表测试样例的个数。

对于每个测试样例，输入一个正整数 N \ (2 \leq N \leq 30)。接下来给出 N 行，每行 N 个以空格间隔的数字来代表格子。这 N \times N 个格子中会有两个 0，分别代表起点和终点。其他数字满足 1 \leq a_{i,j} \leq 10000。

对于每个测试样例，每行输出一个数，代表从起点到终点的最小路程。