本题没有可用的提交语言。

题目描述

考虑一个由 19 个六边形方格组成的游戏棋盘，如下图所示。我们可以很容易地在棋盘形状中区分出三个主要方向：从上到下、从左上角到右下角、从右上角到左下角。对于每个这样的主要方向，棋盘可以看作是一系列的行，分别由 3、4、5、4 和 3 个方格组成。

游戏棋盘必须使用一组六边形棋子完全覆盖。每个棋子带有三个数字，每个主要方向对应一个数字。每个方向仅使用三个不同的数字。对于所有三个方向的每一种三个数字的可能组合都对应一个棋子，从而得到一组 27 个独特的棋子。（上面图中的棋盘仍处于被覆盖的过程中）

棋盘的得分计算为所有 15 行得分的总和（每个主要方向有 5 行）。行得分的计算方式如下：如果一行中的所有棋子在该行对应的方向上带有相同的数字，那么该行得分就是这个数字乘以该行的棋子数量。否则（棋子在该行方向上带有不同的数字）该行得分是零。请注意，棋子不能旋转。例如，图中最左边一行的得分是 3×3 = 9，它右边一行的得分是 4×11 = 44。

在实际游戏中，棋子是随机选择的且棋子集合是固定的，但我们感兴趣的是对于每个方向给定的一组数字，所能得到的最高得分。这意味着你必须选择 19 个能得到最高得分的棋子。

输入格式

输入文件的第一行包含一个整数 n，表示测试用例的数量。每个测试用例由三行组成，每行包含三个整数。这三行中的每一行都包含一个主要方向的数字。根据这些数字生成棋子集合。

输出格式

对于每个测试用例，输出一行，包含用例的编号（“Test #1”、“Test #2” 等），然后是一行，包含给定数字下可能的最高得分。在每个测试用例之后添加一个空行。

1
9 4 3
8 5 2
7 6 1

Test #1
308

提示

在最后时刻的公告中，对该问题添加了以下说明： 为了简化问题，你应该只考虑每行得分都大于零的棋盘，即一行中的每个棋子都带有相同的数字。

来源

1996年西南欧洲区域竞赛