SLF 觉得之前用的地图还是太粗糙了，不能表现出最短路的详细路径。为了让陆地上拖船的脚夫更轻松一点，SLF 让 YDX 画了一张更简单、更详细的地图。这份地图更大，但只由 0 和 1 组成，代表经过该地所耗费的路程。在地图上只能上、下、左、右走，不能走出边界。设地图左上角为起点，右下角为终点。求从起点到终点经过的最短路程。
输入
先输入一个整数 T \ (1 \leq T \leq 10)，代表测试样例的个数。
对于每个测试样例，输入一个正整数 N \ (2 \leq N \leq 500)。接下来给出 N 行，每行 N 个以空格间隔的数字来代表格子。这些数字只由 0 或 1 组成。
输出
对于每个测试样例，每行输出一个数，代表从起点到终点的最小路程（计算路程时计算上起点和终点上的数字）。
样例
| 标准输入 复制文本 |
2 2 1 0 1 1 3 1 0 1 1 1 1 1 0 1 |
| 标准输出 复制文本 |
2 3 |