Маленький Петя готовится к первому контакту с инопланетянами. Он знает, что корабли инопланетян имеют формы невырожденных треугольников и что их будет ровно 4. Посадочная площадка для корабля — это 3 специальных колонны, размещенных в определенных точках плоскости, таких, что эти 3 точки образуют такой же треугольник, как и корабль, с точностью до поворота, параллельного переноса и отражения (симметрий относительно сторон). После посадки корабли могут пересекаться.
Каждая колонна может быть использована чтобы посадить более чем один корабль, например, если есть два одинаковых корабля, то не обязательно строить 6 колонн чтобы посадить оба корабля, достаточно 3. Петя хочет узнать, какого минимального числа колонн будет достаточно, чтобы посадить все корабли.
Выходные данные
Выведите минимальное число колонн, достаточное для посадки всех кораблей.
Примечание
В первом тесте можно поставить колонны в таких точках: (0, 0), (1, 0), (3, 0), (1, 2). Заметьте, что второй корабль может приземлиться, используя последние 3 колонны.
Во втором тесте можно выбрать точки (0, 0), (0, 1), (1, 0), (0, 2), (2, 0), (0, 5), (5, 0), (0, 17), (17, 0). Меньше чем 9 колонн использовать нельзя.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
0 0 1 0 1 2
0 0 0 2 2 2
0 0 3 0 1 2
0 0 3 0 2 2
|
4
|
|
2
|
0 0 0 1 1 1
0 0 0 2 2 2
0 0 0 5 5 5
0 0 0 17 17 17
|
9
|