描述

Chun-Soo正在玩一个骰子堆叠游戏。骰子的六个面都是相同大小的正方形；每个面都有一个从1到6的数字。但是，这些骰子不是标准的，因为对面数字之和可能并不总是7。

骰子游戏的规则是将几个骰子按顺序（骰子$1$，骰子$2$，骰子$3$，...）从底部堆叠起来，同时遵循以下规则：对于每对连续的骰子，顶部骰子的底面数字必须与底部骰子的顶面数字匹配*8。换句话说，接触的两个面必须具有相同的数字。我们可以自由地放置底部骰子**，因此骰子1可以随意设置。

一个具有四个侧面的长矩形柱体被创建出来。我们正在尝试使一个侧面的总和最大。（注意，在旋转骰子以固定顶面和底面后，我们仍然可以将骰子旋转$90$度、$180$度或$270$度。）编写一个程序来找到一个侧面可以具有的最大总和。

输入

输入的第一行包含一个整数 $t$（$1≤t≤11$），表示测试用例的数量，后面是每个测试用例的输入数据。每个测试用例的第一行包含一个整数 $n$$（1≤n≤10,000）$，表示骰子的数量。接下来的行中，每行包含六个整数，表示一个骰子的六个面，按顺序 $A,B,C,D,E,F$给出，如以下图示所示。每两个数字之间有一个空格8。骰子的数量8小于或等于$10,000$。两个骰子可能是相同的。

输出

每个测试用例应有一行输出，其中包含一个侧面的最大数字总和。

样例输入

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

样例输出

29

提示

为了得到上述输入的最大总和，你应该按以下方式堆叠骰子：

来源

德黑兰沙里夫大学2004年初赛