Хуадзи любит наблюдать за звёздами.
В небе есть $$$n$$$ звёзд, которые можно рассматривать как точки на плоскости с декартовыми координатами. Координаты $$$i$$$-й звезды — $$$(x_i, y_i)$$$. Гарантируется, что все $$$x_1, x_2, \ldots, x_n$$$ попарно различны, и все $$$y_1, y_2, \ldots, y_n$$$ попарно различны. Звёзды пронумерованы от $$$1$$$ до $$$n$$$ в порядке, в котором они даны во входных данных.
Хуадзи хочет соединить некоторые пары этих звёзд, чтобы они образовали созвездие.
Она определяет базовую единицу созвездия как треугольник, образованный тремя звёздами, соединёнными попарно. Треугольник называется гармоничным, если существует осевая прямоугольная рамка, такая что все три вершины треугольника лежат на границе этой рамки.
Хуадзи накладывает на созвездие следующие ограничения:
- Каждый треугольник в созвездии должен быть гармоничным.
- Внутренности любых двух треугольников в созвездии не должны пересекаться. Заметьте, что граница треугольника не считается частью его внутренности.
При этих ограничениях Хуадзи хочет, чтобы её созвездие содержало максимально возможное число треугольников. Ваша задача — найти это максимальное число и построить корректное созвездие, которое его достигает.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2\cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных дано одно целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество звёзд.
В следующих $$$n$$$ строках даны по два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$-10^9\le x_i, y_i \le 10^9$$$) — координаты $$$i$$$-й звезды. Гарантируется, что все $$$x_i$$$ попарно различны, и все $$$y_i$$$ попарно различны.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.
В первой строке каждого набора входных данных выведите одно целое число $$$m$$$ ($$$0\le m\le 2\cdot n$$$) — максимальное возможное число треугольников в созвездии.
Затем следуют $$$m$$$ строк, каждая из которых содержит три различных целых положительных числа $$$a_i$$$, $$$b_i$$$ и $$$c_i$$$ ($$$1 \le a_i, b_i, c_i \le n$$$), обозначающие индексы трёх звёзд, образующих $$$i$$$-й треугольник.
28-10 1-2 65 108 -9-1 -23 00 31 -888 8-5 3-4 15 710 10-3 5-8 -10-7 -1
86 5 86 8 41 6 57 1 62 7 13 2 73 7 63 6 422 3 86 2 3
Первый набор входных данных из примера изображён ниже:
Второй набор входных данных из примера изображён ниже:
