소행성 레인저

때는 2112년, 인류는 태양계 전역으로 퍼져 나갔다. 우주 레인저 부대는 태양계 곳곳의 소행성에 기지를 세웠고, 소행성 통신부 소속인 당신의 임무는 모든 기지가 서로 최대한 저렴하게 통신할 수 있도록 하는 것이다.

모든 기지 쌍을 직접 연결하는 것은 비용이 너무 크다. 대신 어떤 기지에서든 (필요하면 중간 기지들을 거쳐) 다른 모든 기지로 메시지를 보낼 수 있도록, 필요한 최소한의 통신 링크만 설치한다. 링크 하나의 비용은 그 링크가 잇는 두 기지 사이의 거리에 비례하므로, 가장 저렴한 통신망은 기지들에 대한 최소 신장 트리(minimum spanning tree)가 된다.

문제는 소행성이 움직인다는 점이다. 지금 가까운 두 기지가 나중에는 멀어질 수 있으므로, 가장 저렴한 통신망은 시간에 따라 바뀔 수 있다. 더 저렴한 통신망이 생길 때마다 당신은 그것으로 교체하며, 교체에는 시간과 비용이 들기 때문에 통신망을 설치하거나 다시 구성해야 하는 횟수를 알고자 한다.

가정: 각 소행성은 하나의 점으로 본다. 모든 소행성은 일정한 속도로 직선 운동을 한다. 두 소행성이 같은 시각에 같은 점에 있는 일은 절대 없다. 시각 $t = 0$에서 가장 저렴한 통신망은 유일하며, 어떤 통신망이 시각 $t \ge 0$에서 가장 저렴해질 때마다 구간 $t < s < t + 10^{-6}$ 동안 유일하게 가장 저렴하다.

당신은 시각 $t = 0$에서 가장 저렴한 통신망을 설치하고, 더 저렴한 통신망이 생길 때마다 그것으로 다시 구성한다. 모든 시각 $t \ge 0$에 걸쳐 통신망을 설치하거나 다시 구성하는 횟수를 구하여라. 이는 최초 통신망 $1$회에, 가장 저렴한 통신망이 바뀌는 매 순간마다 $1$회씩을 더한 값이다. 이전에 쓰였던 통신망이 나중에 다시 가장 저렴해지면 다시 구성할 때마다 별도로 세며, 서로 다른 시각에 나타난 같은 통신망을 하나로 합치지 않는다.

입력은 하나 이상의 테스트 케이스로 이루어지며 파일 끝까지 읽는다.

각 테스트 케이스의 첫 줄에는 소행성 기지의 수를 나타내는 정수 $n$ ($2 \le n \le 50$)이 주어진다. 이어지는 $n$개의 줄에는 각각 여섯 개의 정수 $x$, $y$, $z$, $v_x$, $v_y$, $v_z$가 주어진다. 앞의 세 개는 시각 $0$에서 그 소행성의 위치이고 ($-150 \le x, y, z \le 150$), 뒤의 세 개는 단위 시간당 공간 단위로 나타낸 속도의 $x$, $y$, $z$ 성분이다 ($-100 \le v_x, v_y, v_z \le 100$).

각 테스트 케이스마다 한 줄에 Case X: k를 출력한다. 여기서 $X$는 테스트 케이스 번호($1$부터 시작)이고, $k$는 모든 시각 $t \ge 0$에 걸쳐 통신망을 설치하거나 다시 구성해야 하는 횟수이다.