Рятувальний Маяк#6044
Поки він намагався втекти від своїх старих і не дуже доброзичливих кредиторів, Ган Соло розбив «Тисячолітній сокіл» на крижаній планеті Хот. Тепер йому потрібно якось подати сигнал лиха, щоб його врятували, перш ніж його друг Вуккі стане шерстяною бурулькою. Чи зможете ви йому допомогти?
Ган зумів дістати дуже яскравий лазер, який видно на світлові роки, і подумав, що це стане чудовим сигналом. Недолік у тому, що якщо просто націлити лазер прямо в небо, лише мінімальний шанс, що хтось випадково перебуватиме на шляху променя й побачить сигнал. Тим часом Чубакка грався з купою надзвичайно відбивних, багатогранних кристалів, які він знайшов у печері поруч. І тут, осяяний натхненням, Ган зрозумів, що може зібрати рятувальний маяк, направивши промінь на кристал, грані якого, своєю чергою, відбиватимуть світло в небо у багатьох напрямках!
Рисунок 1: Спрощена двовимірна ілюстрація рятувального маяка Гана.
Єдина проблема, яка залишилась — вирішити, який кристал використати як відбивач світла. Кожен із кристалів — це опуклий поліедр, поверхня якого складається лише з ідеально трикутних граней, і його можна розташувати у маяку у будь-якій орієнтації. Звісно ж, найкращий кристал — той, що відбиватиме лазерний промінь (який складається з паралельних променів світла з одного напрямку) у найбільшу кількість напрямків. Іншими словами, відбивна якість кристала визначається кількістю граней, які видно з будь-якого напрямку спостереження, оскільки саме ці грані одночасно можуть бути досягнуті лазерним променем. Враховуючи опис геометрії кожного кристала, чи зможете ви обчислити найбільшу кількість напрямків, у яких кристал може відбити лазер?
Вхідні дані містять геометричні описи кристалів із колекції Чубакки. Опис кожного кристала починається з цілого числа (4 \leq n \leq 2000) — кількості граней кристала, у першому рядку, після чого йде рядків із описами граней. Кожна грань описується цілими числами: 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 \leq x_i, y_i, z_i \leq 2000. Жодна грань не має площі більше , і жодні дві грані не спрямовані в один і той самий бік. Ви можете бути впевнені, що після складання всіх граней кожного кристала, вони утворюють замкнений опуклий поліедр. Нарешті, жоден кристал не матиме такої структури, яка спричинила б двозначність щодо того, скільки граней можна освітити лазерним променем. Іншими словами, не має значення, чи вважаєте ви грані, паралельні до променя, такими, що можуть відбити промінь, — тестові дані сконструйовано так, що будь-яке трактування дасть один і той же результат. Введення завершується рядком, що містить число (не обробляйте цей тестовий випадок).
Для кожного кристала виведіть в одному рядку одне ціле число : найбільшу кількість напрямків, у які кристал може одночасно відбити лазерний промінь.
Приклад 1