eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Гексагон

Гексагон

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Розглянемо ігрову дошку, яка складається з 19 шестикутних полів як показано на рисунку нижче. Легко виділити три основних напрямки на дошці: зверху вниз, з лівого верху у правий низ та з правого верху у лівий низ. Для кожного з цих основних напрямків дошку можна розглядати як послідовність рядків, які складаються з 3, 4, 5, 4 та 3 полів відповідно.

Ігровое поле повинно бути повністю покрито набором гексагональних фішок. На кожній фішці знаходиться три числа, по одному для кожного напрямку дошки. Три різних числа використовуються для кожного з напрямків. Довільна можлива комбінація з трьох чисел для трьох напрямків може знаходитись на фішці. Таким чином утворюється набір з 27 різних фішок (дошка на рисунку знаходиться у процесі покриття).

Рахунок дошки обчислюється як сума рахунків усіх 15 рядків (по 5 рядків у кожному з основних напрямків). Рахунок рядків обчислюється наступним чином: якщо на усіх фішках у напрямку рядка написано одно і те ж число, то рахунок рядка дорівнює цьому числу, помноженому на кількість полів у рядку. Інакше (на фішках знаходяться різні числа у напрямку рядка) рахунок рядка дорівнює нулю. Фішки не можна обертати. Наприклад, рахунок самого лівого ряду на рисунку дорівнює 3×3 = 9, рахунок ряду праворуч дорівює 4×11 = 44.

Хоча у реальній грі фішки вибираються довільним чином, а їх множина фіксована, Вам потрібно знайти найбільший можливий рахунок для заданого набору чисел у кожному напрямку. Вам необхідно вибрати 19 фішок, які дадуть найбільший рахунок.

Вхідні дані

Перший рядок містить кількість тестів n. Кожен тест складається з трьох рядків по три цілих числа у кожному. Кожен з цих трьох рядків містить числа для одного з основних напрямків. З цих чисел формується набір фішок.

Вихідні дані

Для кожного тесту вивести його номер ('Test #1', 'Test #2' і так далі), за яким у окреиоиу рядку вивести найбільший можливий рахунок для заданих чисел. Сусідні тести відокремлюйте порожнім рядком.

Приклад

Вхідні дані #1
1
9 4 3
8 5 2
7 6 1
Вихідні дані #1
Test #1
308
Джерело Southwest Europe 1996