레이팅 미적용때는 2112년, 인류는 태양계를 정복했다. 우주 레인저 군단은 조금이라도 거주 가능성이 있는 바위 덩어리마다 기지를 세웠다. 소행성 통신부의 일원인 당신의 일은 모든 우주 레인저 소행성 기지가 가능한 한 저렴하게 서로 통신할 수 있게 하는 것이다. 각 기지에서 다른 모든 기지로 직접 통신 링크를 설치할 수도 있지만, 그러면 비용이 엄청나게 든다. 대신 하나 이상의 기지를 거쳐 중계하더라도 모두가 서로에게 메시지를 보낼 수 있도록 최소 개수의 링크를 설치하려 한다. 링크의 비용은 연결하는 두 기지 사이 거리에 정비례하므로 그리 어려운 문제 같지 않다. 하지만 작은 어려움이 하나 있다. 소행성은 움직이는 경향이 있어, 지금 매우 가까운 두 기지가 미래에도 그렇지 않을 수 있다. 따라서 시간이 흐름에 따라 항상 가장 저렴한 중계 시스템이 유지되도록 통신 링크를 기꺼이 교체해야 한다. 링크 교체에는 시간과 돈이 들므로, 이런 교체를 몇 번 수행해야 하는지 알고 싶다. 몇 가지 가정이 일을 쉽게 해 준다. 각 소행성은 하나의 점으로 간주한다. 소행성은 항상 일정한 속도로 직선 운동을 한다. 소행성끼리 충돌하는 일은 없다. 또한 시각 \(t \ge 0\)에 최적이 되는 중계 시스템은 \(t < s < t+10^{ - }^{6}\)를 만족하는 모든 시각 \(s\)에서 유일하게 최적이다. 초기의 최적 중계 시스템은 유일하다.
각 테스트 케이스는 소행성 기지의 수를 나타내는 정수 \(n\) (\(2 \le n \le 50\))이 있는 줄로 시작한다. 다음 \(n\)개의 줄에는 각각 여섯 정수 \(x\), \(y\), \(z\), \(v_{x}\), \(v_{y}\), \(v_{z}\)가 주어진다. 앞의 세 정수는 소행성의 초기 위치(−\(150 \le x\), y, \(z \le 150\))를, 뒤의 세 정수는 시간 단위당 공간 단위로 나타낸 그 소행성 속도의 \(x\), \(y\), \(z\) 성분(−\(100 \le vx\), v\(y\), v\(z \le 100\))을 나타낸다.
각 테스트 케이스마다 케이스 번호와, 중계 시스템을 설치하거나 변경해야 하는 횟수를 한 줄에 출력한다.
3
0 0 0 0 0 0
5 0 0 0 0 0
10 1 0 -1 0 0
4
0 0 0 1 0 0
0 1 0 0 -1 0
1 1 1 3 1 1
-1 -1 2 1 -1 -1
Case 1: 3
Case 2: 3