Space Ant

The most exciting space discovery of the late 20th century happened in 1999, when scientists tracked down an ant-like creature on the planet Y1999 and named it M11. M11 has a single eye on the left side of its head and exactly three feet, all on the right side of its body. Because of this unusual anatomy it walks under three restrictions:

1. It can never turn right.
2. It paints the ground red along every step it takes.
3. It refuses to step onto ground that is already red, so its path never crosses itself.

Photographs from the Discovery spacecraft show that the plants on Y1999 grow only at special points. After analyzing thousands of images, scientists found a magic coordinate system for these growth points: in the plane with the $x$ and $y$ axes, no two plants share the same $x$-coordinate or the same $y$-coordinate.

To stay alive, M11 must eat exactly one plant per day. After eating a plant it rests on that spot for the rest of the day, and the next day it walks to another plant and eats it; it can reach a plant at any distance. If it cannot reach a new plant, it dies at the end of the day.

Let $A$ be the plant with the smallest $y$-coordinate. M11 begins the walk at the point $(0, y_A)$, heading toward $A$. From then on it may make only counter-clockwise (left) turns, and its trail must never cross itself. Under these rules M11 can always eat every plant. Your task is to output the order in which M11 visits the plants.

The visiting order is uniquely determined by the following construction:

• Start at $A$, the plant with the smallest $y$-coordinate.
• At each step, from the current plant choose the next plant $P$ such that every remaining plant lies to the left of the ray from the current plant to $P$; equivalently, $P$ is the most clockwise remaining plant.
• If several remaining plants are collinear on that ray, visit the nearest one first.

The first line contains $M$, the number of test cases ($1 \le M \le 10$). Each test case begins with a line containing $N$, the number of plants ($1 \le N \le 50$). The next $N$ lines each describe one plant with three integers: its unique index (from $1$ to $N$), followed by its $x$- and $y$-coordinates. The plants are listed in increasing order of their indices. All coordinates are positive integers no greater than $100$, and within one test case no two plants share an $x$- or a $y$-coordinate.

For each test case, print one line: first the number of plants on M11's path (which is always $N$), then the indices of the plants in the exact order M11 visits them, all separated by single spaces.