设计者们发明了一种名为“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 之间的整数。

输出格式

对于每个测试用例，输出一行，包含预测的最终得分。

样例

样例输入 1

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

样例输出 1

20
40
63
71