Teleporters (Large)

You are the only yarn manufacturer on the planet Thundera, and you want to get away from work for a while. You decide to travel to the planet Care-a-Lot, the most relaxing planet there is. Your space jetpack is broken, so you cannot move on your own. The only way to travel is the network of interstellar teleporters.

A teleporter is a small machine floating at a fixed point in space. You can use it remotely from any point, however far away you are, but the conservation of teleportation distance principle limits where it can send you. If your L1 distance to the teleporter is $d$ just before you use it, the teleporter sends you to any point whose L1 distance to the teleporter is also exactly $d$. The L1 distance between the points $(x_0, y_0, z_0)$ and $(x_1, y_1, z_1)$ is $|x_0 - x_1| + |y_0 - y_1| + |z_0 - z_1|$.

You start on Thundera. You can use a teleporter to travel from Thundera to a point $p_1$, then use a teleporter to get from $p_1$ to $p_2$, and so on. The last teleportation must take you exactly to Care-a-Lot. You may use the same teleporter more than once, and each use counts as a separate teleportation.

The coordinates in the input are all integers, but an intermediate point you visit may have non-integer coordinates, and no range restriction applies to those points.

You are given the positions of both planets and of every teleporter in 3-dimensional space. Decide whether you can reach Care-a-Lot using only teleporters, and if you can, report the minimum number of teleportations.

The first line gives the number of test cases, $T$. $T$ test cases follow.

Each test case starts with one line containing a single integer $N$, the number of available teleporters. Then $N+2$ lines follow, each containing three integers $X_i$, $Y_i$, and $Z_i$. The first of those lines gives the coordinates of your home planet Thundera, the second gives the coordinates of your destination planet Care-a-Lot, and each of the remaining $N$ lines gives the coordinates of one teleporter.

For each test case, print one line containing Case #x: y, where x is the test case number starting from 1. If you can get from Thundera to Care-a-Lot, y is the minimum number of teleportations needed. If you cannot, print IMPOSSIBLE as y.

• $1 \le T \le 100$
• $1 \le N \le 150$
• $-10^{12} \le X_i \le 10^{12}$
• $-10^{12} \le Y_i \le 10^{12}$
• $-10^{12} \le Z_i \le 10^{12}$
• Within one test case, no two of the described objects, meaning the two planets and the $N$ teleporters, have the same coordinates.

Suppose Thundera is at the origin, Care-a-Lot is at $(0, 4, 0)$, and the only teleporter is at $(0, 3, 0)$. The teleporter is 3 units away from Thundera, so it can only send you to a point that is exactly 3 units away from it, and from such a point it can again only reach points 3 units away from it. Care-a-Lot is 1 unit away from the teleporter, so you can never reach it.

Suppose Thundera is at $(0, 0, 1)$, Care-a-Lot is at $(0, 0, 11)$, and the teleporters are at $(0, 0, 3)$ and $(0, 0, 0)$. Three teleportations are enough. First use the teleporter at $(0, 0, 3)$ to travel to $(0, 0, 5)$. Then use the teleporter at $(0, 0, 0)$ to travel to $(0, 0, -5)$. Finally use the teleporter at $(0, 0, 3)$ again to travel to $(0, 0, 11)$. The two uses of the teleporter at $(0, 0, 3)$ cover different distances because your distance to it differs each time, and they count as two separate teleportations.

Suppose Thundera is at the origin, Care-a-Lot is at $(6, 2, 0)$, and the teleporters are at $(6, 0, 0)$, $(3, 0, 0)$, and $(6, 1, 0)$. Two teleportations are enough. Use the teleporter at $(3, 0, 0)$ to travel to $(6, 0, 0)$, then use the teleporter at $(6, 1, 0)$ to travel to $(6, 2, 0)$. There is a teleporter at $(6, 0, 0)$, but occupying the same point as a teleporter does not count as using it.