Space Ant

20세기 말의 가장 흥미로운 우주 발견은 1999년에 이루어졌다. 과학자들은 행성 Y1999에서 개미를 닮은 생명체를 발견하고 M11이라고 이름 붙였다. M11은 머리 왼쪽에 눈이 하나만 있고, 몸 오른쪽에만 다리가 세 개 있다. 이 특이한 신체 구조 때문에 걸을 때 다음 세 가지 제약을 받는다.

1. 절대 오른쪽으로 돌 수 없다.
2. 지나간 자리마다 바닥을 빨갛게 칠한다.
3. 이미 빨간 바닥은 다시 밟지 않으므로, 이동 경로는 자기 자신과 결코 교차하지 않는다.

디스커버리 우주선이 보낸 사진을 보면 Y1999의 식물은 특정한 점에서만 자란다. 수천 장의 사진을 분석한 결과, 이 식물들의 생장 지점을 지배하는 신비한 좌표계가 밝혀졌다. $x$축과 $y$축으로 이루어진 이 평면에서 어떤 두 식물도 같은 $x$좌표나 같은 $y$좌표를 갖지 않는다.

M11은 살아남기 위해 하루에 정확히 식물 하나를 먹어야 한다. 식물을 먹고 나면 그날 하루는 그 자리에 머무르고, 다음 날 다른 식물로 이동해 그것을 먹는다. 거리에 상관없이 어떤 식물에든 도달할 수 있다. 새로운 식물에 도달할 수 없으면 그날이 끝날 때 죽는다.

$y$좌표가 가장 작은 식물을 $A$라 하자. M11은 점 $(0, y_A)$에서 출발해 $A$를 향해 걷기 시작한다. 그 뒤로는 반시계 방향(왼쪽)으로만 돌 수 있고, 지나온 자취는 결코 교차하지 않는다. 이 규칙 아래에서 M11은 항상 모든 식물을 먹을 수 있다. 당신의 임무는 M11이 식물을 먹는 순서를 출력하는 것이다.

방문 순서는 다음 규칙으로 유일하게 결정된다.

• $y$좌표가 가장 작은 식물 $A$에서 출발한다.
• 매 단계마다 현재 식물에서, 남은 모든 식물이 '현재 식물 → 다음 식물' 방향 반직선의 왼쪽에 놓이도록 하는 식물 $P$를 다음 방문지로 고른다. 즉, 남은 식물 중 가장 시계 방향에 있는 식물을 고른다.
• 그 반직선 위에 남은 식물이 여러 개(한 직선 위에) 있으면 가장 가까운 식물부터 방문한다.

첫째 줄에 테스트 케이스의 수 $M$이 주어진다 ($1 \le M \le 10$). 각 테스트 케이스의 첫 줄에는 식물의 수 $N$이 주어진다 ($1 \le N \le 50$). 이어지는 $N$개의 줄에는 각 식물의 정보가 정수 세 개로 주어지며, 순서대로 식물의 고유 번호($1$부터 $N$까지), $x$좌표, $y$좌표이다. 식물은 번호가 커지는 순서로 주어진다. 모든 좌표는 $100$ 이하의 양의 정수이며, 한 테스트 케이스 안에서 어떤 두 식물도 같은 $x$좌표나 같은 $y$좌표를 갖지 않는다.

각 테스트 케이스마다 한 줄을 출력한다. 먼저 M11의 경로에 있는 식물의 수(항상 $N$이다)를 출력하고, 이어서 M11이 방문하는 순서대로 식물의 번호를 출력한다. 모든 값은 공백 하나로 구분한다.