Hexagon

Consider a game board made of 19 hexagonal fields arranged as shown below. The board has three main directions: from top to bottom, from top-left to bottom-right, and from top-right to bottom-left. Along each direction the board splits into five rows whose lengths are 3, 4, 5, 4, and 3 fields.

The board must be completely covered with hexagonal pieces. Each piece carries three numbers, one for each of the three directions. For every direction only three distinct numbers may appear, so taking one number per direction in every possible combination yields a set of 27 different pieces. Pieces may not be rotated.

The score of a covered board is the sum of its 15 row scores (5 rows in each of the 3 directions). A single row is scored as follows: if every piece in the row shows the same number for that row's direction, the row score is that number multiplied by the number of pieces in the row; otherwise the row score is 0. For example, in the figure the leftmost row scores $3 \times 3 = 9$ and the row immediately to its right scores $4 \times 11 = 44$.

You cover the board by placing exactly 19 of the 27 pieces. For each given set of three numbers per direction, determine the highest total score you can achieve.

The first line contains an integer $n$, the number of test cases. Each test case consists of three lines, each containing three integers. The $k$-th of these three lines lists the three numbers used along the $k$-th direction; the set of 27 pieces is generated from these numbers.

For each test case, print a line Test #k (where $k$ is the test-case number, starting from 1), followed by a line containing the highest achievable score. Separate consecutive test cases with a blank line.