1937: 3326. 最大硬币数

Mike 有一个 N 行 N 列的方格矩阵。

位于第 i行第 j列的方格的位置坐标表示为 (i,j)。

矩阵左上角方格的坐标即为 (1,1)(1,1)。

每个方格中都包含一定数量的硬币，Mike 只有到达一个方格内时，方可收集方格中的硬币。

Ci,j表示第 i行第 j 列的方格中的硬币数量。

当 Mike 处于方格 (i,j) 时，他可以选择移动至方格 (i−1,j−1)或方格 (i+1,j+1)中，前提是所选择的方格位于矩阵边界内，且之前没有到达过。

Mike 可以选择从任意方格开始移动，也可以选择在移动至任意方格时结束移动。

Mike 希望尽可能多的收集硬币。

请帮助他确定他可以收集的最大硬币数量。

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 N。

接下来 N 行，每行包含 N 个整数，其中第 i 行第 j 列的整数表示 Ci,j。

每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: y，其中 x为组别编号（从 1开始），y为可以收集的最大硬币数量。

数据范围

60% 的数据满足，1≤T≤100，1≤N≤100。
另外 40% 的数据满足，1≤T≤10，1≤N≤1000。
100% 的数据满足，0≤Ci,j≤10⁷。

2
3
1 2 5
3 6 1
12 2 7
5
0 0 0 0 0
1 1 1 1 0
2 2 2 8 0
1 1 1 0 0
0 0 0 0 0

Case #1: 14
Case #2: 9

样例解释

对于测试数据 11，Mike 可以选择的行进路径为 (1,1)→(2,2)→(3,3)(1,1)→(2,2)→(3,3)，可收集到的最大硬币数量为 1414。

对于测试数据 22，Mike 可以选择的行进路径为 (2,3)→(3,4)(2,3)→(3,4)，可收集到的最大硬币数量为 99。