题目描述

小约翰正在玩一个骰子叠放游戏。一个骰子的六个面是相同大小的正方形，每个面上标有一个数字，范围是 $1$ 到 $6$。

游戏规则是将若干个骰子按任意顺序叠放起来，但必须遵循以下规则：对于任意两个相邻的骰子，上方骰子的底面数字必须等于下方骰子的顶面数字。换句话说，两个骰子接触的面必须数字相同。

叠放完成后，会形成一个长方体柱，共有四个侧面。我们的目标是让其中一个侧面的数字之和最大化。（注意：在固定一个骰子的顶面和底面后，仍然可以将其旋转 $90^\circ$、$180^\circ$ 或 $270^\circ$。）请编写程序计算可能的最大侧面数字之和。

输入格式

输入的第一行包含一个整数 $t$，表示测试用例的数量。接下来是每个测试用例的输入数据：

• 每个测试用例的第一行是一个整数 $n$（$1 \leq n \leq 10$），表示骰子的数量。
• 接下来的 $n$ 行，每行包含六个整数，表示一个骰子的六个面，顺序为 $A, B, C, D, E, F$，如题目中的图示所示。数字之间用空格分隔。

输出格式

每个测试用例输出一行，表示一个侧面数字的最大和。如果无法将所有骰子叠放起来，则输出 $0$。

示例输入

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 2

示例输出

30

来源

POJ Monthly--2005.08.28, Huang Ninghai