순간이동 장치

아주 짧고 짧은 시간이 흐른 미래, 인근 은하에서, 당신은 Planet Thundera의 유일한 실 제조업자로서의 책임에서 벗어나 잠시 여행을 떠나고 싶어진다. 당신은 그곳에서 가장 편안한 행성인 Planet 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}$|로 주어진다. 불행히도 우주 제트팩이 고장 났으므로 스스로 이동할 수 없으며, 여행하려면 순간이동 장치만 사용할 수 있다. 당신은 Planet Thundera에서 출발한다. 순간이동 장치를 사용하여 Planet Thundera에서 지점 $p_{1}$로 이동한 다음, 다른 장치를 사용하여 $p_{1}$에서 $p_{2}$로 이동하고, 이런 식으로 계속할 수 있다. 마지막 순간이동은 정확히 Planet Care-a-Lot으로 당신을 데려가야 한다.

두 행성과 사용 가능한 모든 순간이동 장치의 3차원 공간상 위치가 주어질 때, 순간이동 장치만 사용하여 여행할 수 있는지 알아내라. 여행할 수 있다면 목적지에 도달하는 데 필요한 최소 순간이동 횟수는 얼마인가? (두 번의 순간이동에서 같은 순간이동 장치를 사용하더라도 별개의 순간이동으로 센다.)

입력은 모든 좌표가 특정 범위 안에 속하는 정수인 점으로 주어진다. 하지만 중간 지점으로는 정수 또는 정수가 아닌 좌표를 가진 지점에 순간이동할 수 있으며, 방문할 수 있는 지점에는 범위 제한이 없다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 모든 i ≠ j에 대해 ($X_{i}$, $Y_{i}$, $Z_{i}$) ≠ ($X_{j}$, $Y_{j}$, $Z_{j}$). (설명된 어떤 두 객체도 같은 좌표를 갖지 않는다.)

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 180초. 1 ≤ N ≤ 100. 모든 i에 대해 -$10^{3}$ ≤ $X_{i}$ ≤ $10^{3}$. 모든 i에 대해 -$10^{3}$ ≤ $Y_{i}$ ≤ $10^{3}$. 모든 i에 대해 -$10^{3}$ ≤ $Z_{i}$ ≤ $10^{3}$.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 360초. 1 ≤ N ≤ 150. 모든 i에 대해 -$10^{12}$ ≤ $X_{i}$ ≤ $10^{12}$. 모든 i에 대해 -$10^{12}$ ≤ $Y_{i}$ ≤ $10^{12}$. 모든 i에 대해 -$10^{12}$ ≤ $Z_{i}$ ≤ $10^{12}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 사용 가능한 순간이동 장치의 수인 하나의 정수 N이 있는 한 줄로 시작한다. 그다음 각각 세 정수 $X_{i}$, $Y_{i}$, $Z_{i}$을 포함하는 N+2개의 줄이 주어진다. 이 줄들 중 첫 번째 줄은 고향 행성 Thundera의 좌표를 나타낸다. 두 번째 줄은 목적지 행성 Care-A-Lot의 좌표를 나타낸다. 나머지 N개의 각 줄은 순간이동 장치 하나의 좌표를 나타낸다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 사용 가능한 순간이동 장치만으로 Thundera에서 Care-A-Lot에 도달할 수 없다면 IMPOSSIBLE이고, 가능하다면 필요한 최소 순간이동 횟수를 나타내는 정수이다.

예제 케이스 #1에서 유일한 순간이동 장치는 Thundera로부터 정확히 3만큼 떨어져 있으며, 이 장치를 사용해서는 순간이동 장치로부터 정확히 3만큼 떨어진 다른 위치로만 갈 수 있다. 그 위치에서도 여전히 순간이동 장치로부터 정확히 3만큼 떨어진 다른 위치에만 도달할 수 있다. Care-a-Lot은 순간이동 장치로부터 1만큼 떨어져 있으므로 절대로 도달할 수 없다.

예제 케이스 #2에서 최적의 전략은 먼저 (0, 0, 3)에 있는 순간이동 장치를 사용하여 (0, 0, 5)로 이동하는 것이다. 그런 다음 그곳에서 (0, 0, 0)에 있는 순간이동 장치를 사용하여 (0, 0, -5)로 이동한다. 마지막으로 그곳에서 (0, 0, 3)에 있는 순간이동 장치를 다시 사용하여 (0, 0, 11)로 이동한다. (0, 0, 3)에 있는 순간이동 장치를 두 번 사용할 때마다 장치로부터 떨어진 거리가 다르므로, 이동하는 거리도 서로 다르다는 점에 유의하라. 또한 이 순간이동 장치를 두 번 사용한 것은 별개의 두 번의 순간이동으로 센다는 점에도 유의하라.

예제 케이스 #3에서 최적의 전략은 먼저 (3, 0, 0)에 있는 순간이동 장치를 사용하여 (6, 0, 0)로 이동하는 것이다. 그런 다음 그곳에서 (6, 1, 0)에 있는 순간이동 장치를 사용하여 (6, 2, 0)로 이동한다. (6, 0, 0)에 순간이동 장치가 있더라도, 단지 순간이동 장치와 같은 지점에 있는 것은 그 장치를 사용한 것으로 세지 않는다는 점에 유의하라.