Гексагон
Рассмотрим игровую доску, состоящую из 19 шестиугольных полей как показано ниже на рисунке. Легко выделить три основных направления на доске: сверху вниз, с левого верха в правый низ и с правого верха в левый низ. Для каждого из этих основных направлений доску можно рассматривать как последовательность строк, состоящих из 3, 4, 5, 4 и 3 полей соответственно.
Игровое поле должно быть полностью покрыто набором гексагональных фишек. На каждой фишке находится три числа, по одному для каждого направления доски. Три разных числа используются для каждого из направлений. Любая возможная комбинация из трех чисел для трех направлений может находиться на фишке. Таким образом образуется набор из 27 различных фишек (доска на рисунке находится в процессе покрытия).
Счет доски вычисляется как сумма счетов всех 15 строк (по 5 строк в каждом из основных направлений). Счет строк вычисляется следующим образом: если на всех фишках в направлении строки написано одно и то же число, то счет строки равен этому числу, умноженному на количество полей в строке. Иначе (на фишках находятся разные числа в направлении строки) счет строки равен нулю. Фишки нельзя вращать. Например, счет самого левого ряда на рисунке равен 3×3 = 9, счет ряда правее равен 4×11 = 44.
Хотя в реальной игре фишки выбираются произвольным образом, а их множество фиксировано, Вам следует найти наибольший возможный счет для заданного набора чисел в каждом направлении. Вам необходимо выбрать 19 фишек, которые дадут наибольший счет.
Входные данные
Первая строка содержит количество тестов n. Каждый тест состоит из трех строк по три целых числа в каждом. Каждая из этих трех строк содержит числа для одного из основных направлений. Из этих чисел формируется набор фишек.
Выходные данные
Для каждого теста вывести его номер ('Test #1', 'Test #2' и так далее), за которым в отдельной строке вывести наибольший возможный счет для данных чисел. Соседние тесты разделяйте пустой строкой.