텔레포터 (스몰)

문제

가까운 미래, 가까운 은하에서 당신은 썬데라(Thundera) 행성의 유일한 실 제조업자다. 잠시 책임에서 벗어나 여행을 떠나고 싶어진 당신은 가장 편안한 행성인 케어어랏(Care-a-Lot)으로 가기로 한다. 이동 수단은 은하 사이에 깔린 텔레포터 망뿐이다.

텔레포터는 우주 어딘가에 떠 있는 작은 기계다. 우주의 어느 지점에서든 원격으로 쓸 수 있지만, 텔레포트 거리 보존 법칙 때문에 이동 직전 당신과 텔레포터 사이의 L1 거리와 정확히 같은 L1 거리에 있는 다른 지점으로만 보내 준다. 두 점 $(x_0, y_0, z_0)$ 과 $(x_1, y_1, z_1)$ 사이의 L1 거리는 $|x_0 - x_1| + |y_0 - y_1| + |z_0 - z_1|$ 이다. 제트팩이 고장 나서 스스로는 움직일 수 없고, 오직 텔레포터로만 이동한다. 출발점은 썬데라다. 텔레포터 하나로 썬데라에서 점 $p_1$ 로 이동하고, 다른 텔레포터로 $p_1$ 에서 $p_2$ 로 이동하는 식으로 계속 갈 수 있다. 마지막 텔레포트는 정확히 케어어랏에 도착해야 한다.

두 행성과 사용할 수 있는 모든 텔레포터의 3차원 좌표가 주어진다. 텔레포터만으로 여행할 수 있는지 판정하고, 할 수 있다면 목적지에 도착하는 데 필요한 텔레포트의 최소 횟수를 구하라. 같은 텔레포터를 두 번 쓰더라도 각각 다른 텔레포트로 센다.

입력으로 주어지는 점의 좌표는 모두 정해진 범위 안의 정수다. 그러나 중간에 거쳐 가는 점의 좌표는 정수가 아니어도 되고, 좌표 범위 제한도 받지 않는다.

입력

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 사용할 수 있는 텔레포터의 개수 $N$ 이 주어진다. 다음 $N + 2$ 개의 줄에는 각각 세 정수 $X_i$ , $Y_i$ , $Z_i$ 가 주어진다. 그중 첫 줄은 고향 행성 썬데라의 좌표, 둘째 줄은 목적지 행성 케어어랏의 좌표이고, 나머지 $N$ 개의 줄은 텔레포터 하나씩의 좌표다.

제한

$1 \le T \le 100$
$1 \le N \le 100$
$-10^3 \le X_i \le 10^3$
$-10^3 \le Y_i \le 10^3$
$-10^3 \le Z_i \le 10^3$
모든 $i \ne j$ 에 대해 $(X_i, Y_i, Z_i) \ne (X_j, Y_j, Z_j)$ 이다. 즉 같은 좌표에 놓인 두 물체는 없다.

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 는 주어진 텔레포터만으로 썬데라에서 케어어랏까지 갈 수 없으면 IMPOSSIBLE, 갈 수 있으면 필요한 텔레포트의 최소 횟수다.

힌트

예제 입력의 첫 번째 테스트 케이스에서 하나뿐인 텔레포터는 썬데라에서 정확히 3만큼 떨어져 있고, 그 텔레포터로는 자신에게서 정확히 3만큼 떨어진 다른 지점으로만 갈 수 있다. 그 지점에서 다시 써도 여전히 텔레포터에서 정확히 3만큼 떨어진 지점에만 도착한다. 케어어랏은 텔레포터에서 1만큼 떨어져 있으므로 영원히 닿을 수 없다.

두 번째 테스트 케이스에서는 먼저 (0, 0, 3)의 텔레포터로 (0, 0, 5)까지 가고, 거기서 (0, 0, 0)의 텔레포터로 (0, 0, -5)까지 간 다음, 마지막으로 (0, 0, 3)의 텔레포터를 다시 써서 (0, 0, 11)로 가는 것이 최적이다. (0, 0, 3)의 텔레포터를 두 번 썼지만 그때마다 텔레포터까지의 거리가 달라서 이동 거리도 다르다. 두 번의 사용은 서로 다른 텔레포트 두 번으로 센다.

세 번째 테스트 케이스에서는 먼저 (3, 0, 0)의 텔레포터로 (6, 0, 0)까지 가고, 거기서 (6, 1, 0)의 텔레포터로 (6, 2, 0)까지 가는 것이 최적이다. (6, 0, 0)에도 텔레포터가 있지만, 텔레포터와 같은 지점에 서 있다고 해서 그 텔레포터를 쓴 것으로 치지는 않는다.