题目描述

给定一个 $3 \times 3$ 的整数网格。记 $G_{i,j}$ 为网格中第 $i$ 行第 $j$ 列的整数，其中 $i$ 和 $j$ 从 $0$ 开始编号。网格正中间的整数 $G_{1,1}$ 缺失。请找出该正方形的行、列和对角线中，能形成等差数列的序列的最大数量。你可以用任意整数替换缺失的数字。

等差数列（也称算术序列）是指一个序列，其中相邻两项的差为常数。用数学术语表示，即 $a_n = a_{n-1} + d$，其中 $d$ 为公差。在本问题中，一个序列可以是某一行、某一列或某一条对角线上的 $3$ 个数。我们希望通过替换缺失值为某个整数，使得最终得到的序列集合中，等差数列的数量最大。

如果两个序列来自不同的行、列或对角线，则视为不同。例如，中间行的序列 $\{2, 4, 6\}$ 与顶行的序列 $\{2, 4, 6\}$ 将算作 $2$ 个序列，但同一行、列或对角线上的序列 $\{2, 4, 6\}$ 与 $\{6, 4, 2\}$ 只算作一个序列。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例由 $3$ 行组成。

每个测试用例的第一行包含 $3$ 个整数：$G_{0,0}$、$G_{0,1}$ 和 $G_{0,2}$。

每个测试用例的第二行包含 $2$ 个整数：$G_{1,0}$ 和 $G_{1,2}$。

每个测试用例的最后一行包含 $3$ 个整数：$G_{2,0}$、$G_{2,1}$ 和 $G_{2,2}$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是在设置缺失元素后，网格的行、列和对角线所能生成的等差数列的最大可能数量。

3
3 4 11
10 9
-1 6 7
4 1 6
3 5
2 5 6
9 9 9
9 9
9 9 9

Case #1: 4
Case #2: 3
Case #3: 8

提示

在样例 #1 中，如果将缺失数字设为 $5$，则恰好有 $4$ 个等差数列。

• 主对角线：$[3, 5, 7]$
• 副对角线：$[-1, 5, 11]$
• 中间列：$[4, 5, 6]$
• 右列：$[11, 9, 7]$

如果将缺失数字设为其他整数，则只会得到 $1$ 个等差数列。因此答案为 $4$。

在样例 #2 中，如果将缺失数字设为 $4$，则恰好有 $3$ 个等差数列。

• 副对角线：$[6, 4, 2]$
• 中间行：$[3, 4, 5]$
• 左列：$[4, 3, 2]$

将缺失数字设为其他任何整数都会导致更少的等差数列，因此输出 $3$。

在样例 #3 中，如果将缺失数字设为 $9$，则所有可能的等差数列都成立。总共有 $8$ 个等差数列（每个都是 $[9, 9, 9]$），因此输出 $8$。

限制条件

$1 \le T \le 100$。

对于所有 $i, j$，$G_{i,j}$ 为整数。

测试集 1

对于所有 $i, j$，$|G_{i,j}| \le 50$。

测试集 2

对于所有 $i, j$，$|G_{i,j}| \le 10^9$。

翻译由 DeepSeek V4 Pro 完成