Цифри на підлозі
Таро намагається передати цифри Ханако, викладаючи прямі палички на підлозі. Він хоче зобразити кожну цифру, створюючи одну з фігур, показаних на Рисунку 1.
Оскільки Таро може не мати паличок потрібної довжини, він не завжди може створити фігури точно так, як показано на Рисунку 1. На щастя, Ханако може розпізнати фігуру як цифру, якщо зберігається зв'язок між паличками у фігурі. Ні довжина паличок, ні напрямок фігур не впливають на сприйняття Ханако, доки зберігається зв'язок. Наприклад, Ханако може розпізнати всі незграбні фігури на Рисунку 2 як цифри. З іншого боку, Ханако не може розпізнати фігури на Рисунку 3 як цифри. Для ясності, дотичні палички трохи розділені на Рисунках 1, 2 і 3. Насправді, дотичні палички перетинаються точно в одній точці.
Рисунок 1: Представлення цифр
Рисунок 2: Приклади форм, що розпізнаються як цифри
У фігурах, коли одна паличка торкається іншої, точка дотику є кінцем принаймні однієї з них. Тобто палички ніколи не перетинаються. Крім того, кут між такими двома паличками завжди є прямим.
Щоб Таро міг представляти фігури з обмеженим набором паличок, положення і довжини паличок можуть змінюватися, якщо зберігаються зв'язки. Також фігури можуть бути повернуті.
Збереження зв'язків означає наступне.
Рисунок 3: Форми, що не розпізнаються як цифри (такі форми не містяться в наборі даних)
Розділені палички не робляться дотичними.
Дотичні палички не розділяються.
Коли один кінець палички торкається іншої палички, цей кінець все ще торкається тієї ж палички. Коли він торкається середини іншої палички, він залишається торкатися середини тієї ж палички з того ж боку.
Кут дотику двох паличок зберігається як той самий прямий кут (90 градусів і −90 градусів вважаються різними, і форми для 2 і 5 залишаються відмінними).
Ваше завдання - визначити, скільки разів кожна цифра з'являється на підлозі.
Форми деяких цифр завжди містять форми інших цифр. Наприклад, форма для 9 завжди містить чотири форми для 1, одну форму для 4 і дві накладені форми для 7. У цій задачі ігноруйте форми, що містяться в іншій формі, і рахуйте лише цифру "найбільшої" форми, складеної з усіх взаємопов'язаних паличок. Якщо є одна форма для 9, це слід інтерпретувати як одну появу 9 і жодної появи 1, 4 або 7.
Вхідні дані
Вхід складається з кількох наборів даних. Кожен набір даних відформатований наступним чином.
n
x_1a y_1a x_1b y_1b
x_2a y_2a x_2b y_2b
...
x_na y_na x_nb y_nb
У першому рядку n представляє кількість паличок у наборі даних. Для решти рядків один рядок представляє одну паличку. Чотири цілі числа x_a, y_a, x_b, y_b, розділені пробілами, подані в кожному рядку. x_a і y_a є x- та y-координатами одного кінця палички відповідно. x_b і y_b є координатами іншого кінця. Система координат показана на Рисунку 4. Ви можете припустити, що 1 ≤ n ≤ 1000 і 0 ≤ x_a, y_a, x_b, y_b ≤ 1000.
Кінець вводу позначається рядком, що містить один нуль.
Рисунок 4: Система координат
Ви також можете припустити наступні умови.
Більше двох паличок не перетинаються в одній точці.
Кожна паличка використовується як частина цифри. Нецифрові форми не існують на підлозі.
Паличка, що складає одну цифру, не торкається і не перетинає жодну паличку, що складає іншу цифру.
Немає палички, довжина якої дорівнює нулю.
Вихідні дані
Для кожного набору даних виведіть один рядок, що містить десять цілих чисел, розділених пробілами. Ці числа представляють, скільки разів 0, 1, 2, ..., і 9 з'являються на підлозі в цьому порядку. Рядки виводу не повинні містити інших символів.