월리 월드

이루어지기 힘든 두 연인이 서로 만나려고 한다. 두 연인은 평면 위의 서로 다른 두 점에 서 있다. 그들은 자유롭게 이동할 수 있지만, 절대로 넘을 수 없는 벽 하나가 있다. 이 벽은 $x$축 또는 $y$축에 평행한 선분이다. 각 연인은 1초에 1의 거리만큼 움직일 수 있다. 두 사람이 각자 가장 좋은 경로를 선택한다면, 함께 만나기까지 얼마의 시간이 걸리겠는가?

각 테스트 케이스는 두 줄로 이루어지며, 각 줄에는 네 개의 정수가 있다. 첫 줄의 처음 두 정수는 첫 번째 연인의 $x$, $y$ 좌표이고, 다음 두 정수는 두 번째 연인의 $x$, $y$ 좌표이다. 둘째 줄의 네 정수는 벽의 시작점과 끝점 좌표를 나타낸다.

또한 모든 경우에서 두 연인 모두 벽을 포함하는 (무한히 뻗은) 직선, 즉 벽을 양쪽으로 연장한 직선 위에 있지 않다. 모든 좌표는 양수이며 $10000$ 이하이고, 어느 연인도 벽 위에서 출발하지 않는다. 입력의 끝은 네 개의 $0$으로 이루어진 줄로 표시된다.

각 테스트 케이스마다 두 연인이 만나는 데 걸리는 최소 시간을 초 단위로 출력한다. 답은 소수점 아래 정확히 셋째 자리까지 출력하며, 각 줄은 다음 형식을 따른다.

Case n: t

여기서 $n$은 1부터 시작하는 테스트 케이스 번호이고, $t$는 최소 시간이다.