描述

现在小Q和小T要开始玩淘金棋，他们都想成为最强的棋士。

淘金棋的棋盘是 \(4\times 4\) 的方格，初始的时候每一个方格都放置了若干数量的金币。小Q先操作，之后是小T操作，二人交替操作。他们总计要操作 \(2k\) 次。

有一个记分牌子，一开始记分是零分。

对于一个玩家来说，他的每一次操作都可以选择一个 \(2\times 2\)的子区域，并将与这个子区域内金币数量相同的分数加到记分牌上，之后把这四个格子逆时针旋转 \(90\) 度（也就是修改了他们中金币的数量）。小Q的最终目的是最大化这个记分牌上的分数，而小T的最终目标是最小化这个记分牌上的分数。

已经知道小Q和小T都极致聪明，下面希望你能预测一下最终记分牌的得分。

格式

输入格式

输入含有多组数据，其中第一行给定一个整数 \(T~(1\le T\le 8)\) 表示之后会给出 \(T\) 组数据。

对于每一组数据，一共有五行，其中第一行给定了正整数 \(k\)，表示他们二人分别要操作 \(k\) 次。

之后的四行中，每一行都给出四个正整数，描述了初始棋盘上金币的数量。

输出格式

一共输出 \(T\) 行，分别对应了 \(T\) 组数据，分别为每一组数据中预测的最终记分板上的数。

样例1

样例输入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

限制

对于 \(10\%\) 的数据，满足 \(1\le k\le 3\)。

对于 \(30\%\) 的数据，满足 \(1\le k\le 4\)。

对于 \(60\%\) 的数据，满足 \(1\le k\le 5\)。

对于 \(100\%\) 的数据，满足 \(1\le T\le 8\) 且 \(1\le k\le 6\)，所有格子最初的金币个数一定是 \(1\) 到 \(10\) 的整数。

每一组数据时限为2秒。