题目描述

Mike 有一个 $N$ 行 $N$ 列的方阵。单元格 $(i, j)$ 表示第 $i$ 行第 $j$ 列的格子。单元格 $(1, 1)$ 表示矩阵的左上角。每个格子中有一定数量的硬币，Mike 只有访问该格子时才能收集它们。$C_{i, j}$ 表示第 $i$ 行第 $j$ 列格子中的硬币数。从格子 $(i, j)$ 出发，Mike 可以决定移动到 $(i+1, j+1)$ 或 $(i-1, j-1)$，只要该格子仍在矩阵边界内且尚未被访问过。他可以选择从任意格子开始，并在任意时刻停止。Mike 希望最大化他能收集到的硬币总数。请帮助他确定能收集到的最大硬币数。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$。接下来的 $N$ 行，每行包含 $N$ 个整数。第 $i$ 行的第 $j$ 个整数表示单元格 $(i, j)$ 中的硬币数 $C_{i, j}$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Mike 能收集到的最大硬币数。

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

提示

在样例 #1 中，如果 Mike 沿着路径 $(1,1) \to (2,2) \to (3,3)$ 行走，他最多可以收集到 $14$ 枚硬币。

在样例 #2 中，如果 Mike 沿着路径 $(2,3) \to (3,4)$ 行走，他最多可以收集到 $9$ 枚硬币。

限制条件

$1 \le T \le 100$。

$0 \le C_{i, j} \le 10^7$。

测试集 1

$1 \le N \le 100$。

测试集 2

最多 $10$ 个测试用例满足 $1 \le N \le 10^3$。

其余所有测试用例满足 $1 \le N \le 100$。

翻译由 DeepSeek V4 Pro 完成