Asteroid Rangers

The year is 2112 and humankind has spread across the solar system. The Space Ranger Corps have built bases on asteroids throughout the system, and your job at the Asteroid Communications Ministry is to keep every base able to communicate with every other base as cheaply as possible.

You will not connect every pair of bases directly, because that would be far too expensive. Instead you build the smallest number of communication links so that any base can reach any other base, possibly relayed through intermediate bases. The cost of a link is proportional to the distance between the two bases it connects, so the cheapest network is a minimum spanning tree over the bases.

The catch is that asteroids move. Two bases that are close now may drift apart later, so the cheapest network can change over time. Whenever a cheaper network becomes available you switch to it, and because switching costs time and money you want to know how many times the network has to be built or rebuilt.

Assumptions: each asteroid is a single point; every asteroid moves in a straight line at constant velocity; no two asteroids ever occupy the same point at the same time. The cheapest network at time $t = 0$ is unique, and whenever a network becomes cheapest at some time $t \ge 0$ it is the unique cheapest network throughout the interval $t < s < t + 10^{-6}$.

You set up the cheapest network at time $t = 0$ and rebuild it every time a strictly cheaper network becomes available. Report how many times the network is set up or rebuilt over all time $t \ge 0$: this is $1$ for the initial network plus $1$ for each moment at which the cheapest network changes. A network that was used before and later becomes cheapest again is counted every time it is rebuilt, so equal networks appearing at different times are not merged.

The input contains one or more test cases and is read until end of file.

Each test case begins with a line containing an integer $n$ ($2 \le n \le 50$), the number of asteroid bases. Each of the next $n$ lines contains six integers $x$, $y$, $z$, $v_x$, $v_y$, $v_z$: the first three give the base's position at time $0$ ($-150 \le x, y, z \le 150$) and the last three give its velocity in space units per time unit ($-100 \le v_x, v_y, v_z \le 100$).

For each test case, print a single line Case X: k, where $X$ is the test case number (starting from $1$) and $k$ is the number of times the communication network has to be built or rebuilt over all time $t \ge 0$.