구조 신호기

한 솔로는 빚쟁이들을 피해 달아나다가 밀레니엄 팔콘호를 얼음 행성 호스에 불시착시켰다. 동료 우키인 츄바카가 얼어붙거나 배고픔에 지쳐 "한 솔로 꼬치"라도 먹고 싶어지기 전에, 그는 어떻게든 구조 신호를 보낼 방법을 찾아야 한다. 도와줄 수 있겠는가?

한 솔로는 몇 광년 밖에서도 보이는 아주 밝은 레이저를 구했고, 이것이 좋은 신호가 되리라 생각했다. 문제는, 레이저를 하늘로 곧장 쏘아 올려 봤자 마침 그 빛줄기의 경로에 누군가가 있어 알아챌 확률은 거의 없다는 점이다. 그때 츄바카는 근처 동굴에서 찾은, 반사율이 높고 여러 삼각형 면을 가진 결정들을 가지고 놀고 있었다. 순간 한 솔로에게 영감이 떠올랐다. 레이저를 결정에 비추면, 결정의 여러 면이 빛을 한꺼번에 사방으로 반사시켜 훌륭한 구조 신호기가 될 것이다!

그림 1: 한 솔로의 구조 신호기를 2차원으로 단순화한 그림.

이제 남은 문제는 어떤 결정을 반사체로 쓸지 정하는 것이다. 각 결정은 표면이 완전한 삼각형 면들로만 이루어진 볼록 다면체이며, 어떤 방향으로든 자유롭게 놓을 수 있다. 가장 좋은 결정은 레이저(한 방향에서 들어오는 평행 광선)를 가장 많은 방향으로 되쏘아 주는 것이다. 다시 말해, 결정의 반사 성능은 "어떤 한 시선 방향에서 동시에 보이는 면의 개수"로 볼 수 있다. 그 면들이야말로 레이저에 동시에 맞을 수 있는 면들이기 때문이다. 각 결정의 기하 구조가 주어질 때, 그 결정이 레이저를 동시에 반사할 수 있는 방향의 최대 개수를 구하여라.

입력은 츄바카가 모은 결정들의 기하 정보로 이루어진다. 각 결정의 정보는 면의 개수를 나타내는 정수 $n$ ($4 \le n \le 2000$)이 한 줄에 주어지는 것으로 시작하고, 이어서 $n$개의 줄에 각 면의 정보가 주어진다. 각 면은 9개의 정수 $x_1\ y_1\ z_1\ x_2\ y_2\ z_2\ x_3\ y_3\ z_3$으로 표현되며, 세 점 $(x_1, y_1, z_1)$, $(x_2, y_2, z_2)$, $(x_3, y_3, z_3)$은 그 삼각형 면의 세 꼭짓점이다. 이 꼭짓점들은 (오른손 좌표계에서) 면을 바깥쪽에서 보았을 때 반시계 방향 순서로 주어진다. 모든 좌표는 $-2000 \le x_i, y_i, z_i \le 2000$ 범위 안에 있고, 넓이가 200,000을 넘는 면은 없으며, 서로 같은 방향을 향하는 두 면은 없다. 한 결정의 모든 면을 조립하면 항상 닫힌 볼록 다면체를 이룬다. 또한 어떤 결정도 레이저가 맞힐 수 있는 면의 개수를 모호하게 만드는 퇴화(degenerate) 구조를 가지지 않는다. 즉, 레이저 빔과 정확히 평행한 면을 반사 가능한 면으로 볼지 말지가 답에 영향을 주지 않도록 데이터가 구성되어 있다. 입력의 끝은 정수 $0$ 하나만 있는 줄로 표시되며, 이 줄은 결정으로 처리하지 않는다.

각 결정마다 한 줄에 정수 $m$ 하나를 출력한다. $m$은 그 결정이 레이저를 동시에 반사할 수 있는 방향(면)의 최대 개수이다.