보급 임무

바다 위를 이동하는 여러 척의 잠수함에 물자를 전달하기 위해 헬리콥터를 조종해야 합니다.

헬리콥터 기지의 좌표와 각 잠수함의 좌표가 주어집니다. $i$번째 잠수함은 속도 벡터 $(v_x, v_y)$로 일정하게 이동합니다. 즉 한 시간이 지나면 x축 방향으로 $v_x$ km, y축 방향으로 $v_y$ km 이동합니다($v_x$와 $v_y$는 음수일 수 있습니다). 이 벡터의 길이가 잠수함의 속력입니다.

헬리콥터는 어느 방향으로든 일정한 속력으로 이동합니다(가속과 감속은 즉시 이루어진다고 가정합니다). 헬리콥터는 각 잠수함에 최소 한 번은 착륙해야 하며, 착륙할 때마다 물자를 내리고 연료를 채우는 데 정확히 한 시간이 걸립니다. 잠수함은 착륙 예정 시각에 수면으로 떠오르고 헬리콥터가 떠나면 다시 잠수합니다. 잠수함의 속도는 잠수 깊이에 영향을 받지 않습니다. 한 시간 동안 머무르는 사이에도 헬리콥터는 잠수함 위에 있으므로 잠수함과 함께 같은 속도로 이동합니다. 헬리콥터는 모든 잠수함에 나눠 줄 물자를 한 번에 실을 수 있어, 임무 중간에 기지로 돌아올 필요가 없습니다.

모든 좌표의 단위는 km이고, 모든 속력의 단위는 km/h입니다.

헬리콥터가 기지에서 출발하여 모든 잠수함에 물자를 전달하고 다시 기지로 돌아오는 데 걸리는 최소 시간을 구하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다.

각 테스트 케이스는 잠수함의 수를 나타내는 정수 $N$($1 \le N \le 8$)이 적힌 줄로 시작합니다. 다음 $N$개의 줄에는 공백으로 구분된 네 정수, 즉 해당 잠수함의 초기 좌표 $x$, $y$와 속도 성분 $v_x$, $v_y$가 주어집니다. 테스트 케이스의 마지막 줄에는 세 정수, 즉 헬리콥터 기지의 좌표 $x$, $y$와 헬리콥터의 속력이 주어집니다.

입력의 끝은 첫 줄이 $N = 0$인 테스트 케이스로 표시되며, 이 케이스는 처리하지 않습니다.

입력에 등장하는 모든 정수의 절댓값은 $1000$ 이하입니다. 헬리콥터는 항상 모든 잠수함보다 빠릅니다. 잠수함들의 경로는 서로 교차하거나 기지를 지날 수도 있지만, 깊이를 조절할 수 있으므로 충돌은 일어나지 않습니다.

각 테스트 케이스마다 케이스 번호와 임무를 완수하는 데 필요한 최소 시간을 다음 형식으로 출력합니다.

Case a: b hour(s) c minute(s) d second(s)

여기서 $a$, $b$, $c$, $d$는 음이 아닌 정수이며 $c$와 $d$는 $59$ 이하입니다. 시간은 다음 초 단위로 올림합니다.