텔레포터 (대규모)

당신은 선더라 행성에서 실을 만드는 유일한 제조업자다. 잠시 일에서 벗어나고 싶어진 당신은 가장 편안한 행성인 케어어랏으로 여행을 떠나기로 했다. 제트팩이 고장 나서 스스로는 움직일 수 없고, 성간 텔레포터 망만 이용할 수 있다.

텔레포터는 우주 공간의 한 지점에 떠 있는 작은 기계다. 아무리 멀리 떨어져 있어도 원격으로 쓸 수 있지만, 텔레포트 거리 보존 법칙 때문에 이동 방식이 제한된다. 텔레포터를 쓰기 직전 당신과 그 텔레포터 사이의 L1 거리가 $d$였다면, 텔레포터는 자신과의 L1 거리가 정확히 $d$인 임의의 지점으로 당신을 보낸다. 두 점 $(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$개의 줄은 각각 텔레포터 하나의 좌표다.

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

• $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}$
• 한 테스트 케이스에서 좌표로 설명하는 물체, 즉 두 행성과 $N$개의 텔레포터는 어느 둘도 좌표가 같지 않다.

선더라가 원점, 케어어랏이 $(0, 4, 0)$, 유일한 텔레포터가 $(0, 3, 0)$에 있다고 하자. 이 텔레포터는 선더라에서 3만큼 떨어져 있으므로 자신과의 거리가 정확히 3인 지점으로만 당신을 보낼 수 있고, 그렇게 도착한 지점에서 다시 써도 마찬가지로 거리가 3인 지점에만 갈 수 있다. 케어어랏은 이 텔레포터에서 1만큼 떨어져 있으므로 영영 도착할 수 없다.

선더라가 $(0, 0, 1)$, 케어어랏이 $(0, 0, 11)$, 텔레포터가 $(0, 0, 3)$과 $(0, 0, 0)$에 있다고 하자. 세 번이면 충분하다. 먼저 $(0, 0, 3)$의 텔레포터로 $(0, 0, 5)$로 가고, 거기서 $(0, 0, 0)$의 텔레포터로 $(0, 0, -5)$로 간 다음, 다시 $(0, 0, 3)$의 텔레포터로 $(0, 0, 11)$로 간다. $(0, 0, 3)$의 텔레포터를 두 번 쓸 때 이동 거리가 서로 다른 이유는 두 경우에 그 텔레포터까지의 거리가 다르기 때문이다. 이 두 번은 별개의 텔레포트로 센다.

선더라가 원점, 케어어랏이 $(6, 2, 0)$, 텔레포터가 $(6, 0, 0)$, $(3, 0, 0)$, $(6, 1, 0)$에 있다고 하자. 두 번이면 충분하다. $(3, 0, 0)$의 텔레포터로 $(6, 0, 0)$으로 간 다음, $(6, 1, 0)$의 텔레포터로 $(6, 2, 0)$으로 간다. $(6, 0, 0)$에 텔레포터가 있지만, 텔레포터와 같은 지점에 있는 것만으로는 그 텔레포터를 쓴 것이 아니다.