Рятувальний Маяк
Під час спроби уникнути деяких старих і не дуже задоволених кредиторів, Хан Соло розбив "Тисячолітній сокіл" на крижаній планеті Хот. Тепер він повинен запустити аварійний сигнал, щоб його врятували, перш ніж його друг Вукі стане хутряним льодяником або вирішить з'їсти "Хан-шашлик". Чи можете ви йому допомогти?
Хан зміг врятувати дуже яскравий лазер, який можна побачити з відстані світлових років, і подумав, що це буде хороший сигнал. Недолік полягає в тому, що якщо він просто направить його прямо в небо, буде лише мінімальний шанс, що хтось випадково опиниться на шляху світла, щоб його побачити. Тим часом Чубакка грався з купою високо відбивних, багатогранних кристалів, які знайшов у печері неподалік. Потім, у момент натхнення, Хан зрозумів, що може зібрати рятувальний маяк, направивши світло вниз на кристал, чиї грані, в свою чергу, відбиватимуть світло в небо в безлічі напрямків!
Рисунок 1: Спрощена, двовимірна ілюстрація рятувального маяка Хана.
Єдина проблема, що залишається, - це вибір кристала для використання як відбивача світла. Кожен з відбивних кристалів має форму опуклого багатогранника, поверхня якого складається виключно з ідеально трикутних граней, і може бути встановлений у маяк в будь-якій орієнтації. Звичайно, найкращий кристал для використання - це той, який відбиватиме лазерний промінь (який складається з паралельних світлових променів з одного напрямку) назад у найбільшу кількість напрямків. Іншими словами, ви можете вважати відбивну здатність кристала просто кількістю граней на ньому, які можна побачити з будь-якого одного напрямку огляду, оскільки саме ці грані можуть бути одночасно вражені лазерним променем. Враховуючи опис геометрії кожного з кристалів, чи можете ви обчислити найбільшу кількість напрямків, у яких кристал може відбити лазер?
Вхідні дані
Вхідні дані складатимуться з геометричних описів кристалів у колекції Чубакки. Опис кожного кристала починається з цілого числа n (4 ≤ n ≤ 2000), кількості граней на кристалі, на одному рядку, за яким слідують n рядків, що описують грані. Кожна грань описується 9 цілими числами, x_1 y_1 z_1 x_2 y_2 z_2 x_3 y_3 z_3, де точки (x_1, y_1, z_1), (x_2, y_2, z_2) і (x_3, y_3, z_3) в тривимірному просторі утворюють вершини трикутної грані в проти годинникової стрілки (в правій системі координат) при огляді ззовні. Всі координати знаходяться в діапазоні -2000 ≤ x_i, y_i, z_i ≤ 2000, жодна окрема грань не має площі поверхні більше 200000, і жодні дві грані не спрямовані в одному напрямку. Ви можете очікувати, що коли всі грані кожного кристала зібрані, вони утворюють закритий опуклий багатогранник. Нарешті, жоден кристал не матиме структури з будь-якою виродженістю, яка могла б викликати неоднозначність щодо того, скільки граней може вразити лазер. Іншими словами, не має значення, чи вважаєте ви грані, паралельні лазерному променю, здатними відбивати промінь чи ні - тестові дані були складені таким чином, що будь-яка інтерпретація дала б однакову відповідь. Іншими словами, не має значення, чи вважаєте ви грані, паралельні лазерному променю, здатними відбивати світло чи ні. Вхідні дані завершуються рядком, що містить число 0 (не обробляйте це як тестовий випадок).
Вихідні дані
Для кожного кристала виведіть в одному рядку ціле число m: найбільшу кількість напрямків, у яких кристал може одночасно відбити лазерний промінь.