题目描述

设计师们想出了一款新的简单游戏，名为 “Rake It In”。游戏有两名玩家，Alice 和 Bob，他们首先选定一个整数 $k$ 并初始化一个得分指示器。在一个 $4 \times 4$ 的棋盘上放置 $16$ 个数值。从玩家 Alice 开始，每轮每位玩家在棋盘上选择一个 $2 \times 2$ 的区域，将该区域内数值之和加到得分指示器上，然后将这四个数值逆时针旋转 $90$ 度。

总计进行 $2k$ 轮后，每名玩家各做了 $k$ 次决策。Alice 的最终目标是最大化最终得分，而 Bob 的目标则是最小化最终得分。

为了测试这款游戏有多好，你被聘请编写一个能够进行该游戏的程序。具体来说，给定起始局面，他们需要一个程序来确定当双方玩家完全理性时的最终得分。

输入格式

输入包含多个测试用例，第一行给出一个整数 $t$ ($1 \le t \le 200$)，表示测试用例的数量。

每个测试用例包含五行。第一行给出整数 $k$ ($1 \le k \le 3$)。接下来的四行每行包含四个整数，表示棋盘初始时的数值。所有数值均为 $1$ 到 $10$ 之间的整数。

输出格式

对于每个测试用例，在一行中输出一个整数，即预测的最终得分。

4
1
1 1 2 2
1 1 2 2  
3 3 4 4  
3 3 4 4
2
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
3  
1 1 4 4
4 4 1 1
1 1 4 4
1 4 1 4
3  
1 2 3 4
5 1 2 3
4 5 1 2
3 4 5 1

20
40
63
71

提示

翻译由 DeepSeek V4 Pro 完成