Rebel Against The Empire (Small)

문제

당신은 사악한 은하 제국에 맞서는 반란군이며, 지금 도망치는 중이다!

당신은 제국의 악의 공장을 파괴했고, 곧 제국 보안군이 뒤쫓아 올 것이다. 공장은 번호가 매겨진 $N$ 개의 소행성으로 이루어진 성계의 0번 소행성에 있다. 탈출선 센추리 퀘일은 1번 소행성에 있고, 그곳에 도착하면 안전하게 날아서 떠날 수 있다.

각 소행성은 속도가 있는 공간 속의 한 점이며, 당신은 지금 올라타 있는 소행성과 함께 움직인다. 소행성 점퍼를 쓰면 성계 안의 어느 두 소행성 사이든 순간적으로 점프할 수 있다. 먼 점프는 가까운 점프보다 무섭기 때문에(게다가 우주의 진공은 끔찍하다) 당신은 점프해야 하는 최대 거리를 최소로 만들고 싶다. 그런데 지금부터 점프하지 않고 연속으로 $S$ 초보다 오래 머무르면 제국 보안군에게 붙잡힌다. 즉 지금부터 첫 점프까지의 시간 간격과 이어지는 두 점프 사이의 시간 간격은 모두 $S$ 이하여야 한다. 점프는 어느 순간에나 할 수 있으며, 정수 초가 지난 시점일 필요는 없다. 1번 소행성으로 점프하는 순간 탈출에 성공한다.

$i$ 번 소행성은 공간의 위치 $(x_i, y_i, z_i)$ 에서 출발하고, 1초마다 총 $(Vx_i, Vy_i, Vz_i)$ 만큼 이동한다. 이 이동은 시간에 따라 연속적으로 일어나며, 1초마다 한 번씩 끊어서 갱신되는 것이 아니다. (소행성이 정지해 있을 수도 있다.) 여러 소행성이 같은 시각에 같은 점에 있어도 아무 일도 일어나지 않는다. 두 소행성 사이는 점프로만 이동할 수 있으며, 점프하는 순간 두 소행성이 같은 점에 있더라도 마찬가지다.

이 버전(Small)에서는 모든 소행성이 정지해 있다.

최대 점프 거리를 최소로 만드는 탈출 계획에서 그 최대 점프 거리는 얼마인가?

입력

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 두 정수 $N$ (소행성의 수)과 $S$ (점프하지 않고 버틸 수 있는 시간의 한도)가 주어진다. 다음 $N$ 개의 줄에는 소행성의 정보가 주어진다. 그중 $i$ 번째 줄(0부터 센다)에는 여섯 정수가 주어진다. 앞의 세 수는 $i$ 번 소행성의 처음 위치 $(x_i, y_i, z_i)$ 이고, 뒤의 세 수는 1초 동안 이동하는 거리 $(Vx_i, Vy_i, Vz_i)$ 이다.

제한

$1 \le T \le 20$
$2 \le N \le 1000$
$1 \le S \le 100$
$-500 \le x_i \le 500$
$-500 \le y_i \le 500$
$-500 \le z_i \le 500$
$Vx_i = 0$
$Vy_i = 0$
$Vz_i = 0$

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 탈출하려면 해야 하는 가장 긴 점프의 거리이다.

y는 정확한 값을 반올림해서 소수점 아래 정확히 7자리로 출력한다. 정확한 값은 항상 어떤 정수의 제곱근이므로 반올림 결과는 하나로 정해진다.

힌트

예제에서는 정지한 소행성 $(0, 0, 0)$ 에서 출발하고, 탈출선은 $(1, 2, 2)$ 에 있는 소행성에 있다. 다른 소행성 하나가 $(1, 1, 1)$ 에 있다. 탈출선으로 곧바로 점프하면 거리가 3이다. 다른 소행성으로 거리 $\sqrt{3}$ 만큼 점프한 뒤 그곳에서 탈출선으로 거리 $\sqrt{2}$ 만큼 점프할 수도 있다. 최대 점프 거리는 첫 번째 방법이 3, 두 번째 방법이 $\sqrt{3}$ 이므로 두 번째 방법이 낫다.

이 버전에서는 S의 값이 결과에 영향을 주지 않는다. 모든 소행성이 정지해 있으므로 기다릴 이유가 없고, 모든 점프를 즉시 할 수 있다.