정육면체 콜로니

서기 3456년, 지구는 수천억 명이 평화롭게 살기에는 너무 좁다. 큐브 성간 이주 계획(Interstellar Colonization Project with Cubes, ICPC)은 이 문제를 덜려고 지구의 사람을 우주 콜로니로 옮기는 계획이다. ICPC는 여러 정부에서 예산을 받아, 미리 만들어 둔 정육면체 블록으로 우주 콜로니를 아주 빠르고 싸게 지었다.

가장 큰 콜로니는 루빅스 큐브처럼 생겼다. 정육면체 블록 $3 \times 3 \times 3$개로 이루어진다(그림 J.1A). 더 작은 콜로니는 여기서 블록 몇 개가 빠진 모양이다.

블록 여러 개로 콜로니를 만들 때는 블록 하나에서 시작한다. 그다음 이미 놓인 블록에 새 블록의 면을 정확히 맞춰 붙이는 일을 반복한다. 맞닿은 면은 모두 접착된다.

그림 J.1: 가장 큰 콜로니와 더 작은 콜로니

그런데 첫 발사를 앞두고 설계 결함을 발견했다. 콜로니마다 표면 위의 두 점을 케이블로 이어야 하는데, 미리 만든 블록의 내부는 짧은 시간에 바꿀 수 없다. 그래서 케이블을 콜로니 표면에 붙이기로 했다. 케이블이 표면에서 조금이라도 떨어져 있으면 발사 중에 잘려 나가므로, 케이블 전체가 표면 위에 놓여야 한다. 예산이 빠듯해서 케이블 길이는 최소로 줄여야 한다. 그림 J.1B의 점선이 그런 케이블이다. 콜로니의 모양과 표면 위의 두 점이 주어질 때, 그 콜로니에 필요한 가장 짧은 케이블의 길이를 구하는 프로그램을 작성하시오.

입력은 데이터셋 여러 개로 이루어진다. 각 데이터셋은 콜로니 하나와 그 표면 위의 두 점을 다음 형식으로 나타낸다.

x1 y1 z1 x2 y2 z2
b0,0,0 b1,0,0 b2,0,0
b0,1,0 b1,1,0 b2,1,0
b0,2,0 b1,2,0 b2,2,0
b0,0,1 b1,0,1 b2,0,1
b0,1,1 b1,1,1 b2,1,1
b0,2,1 b1,2,1 b2,2,1
b0,0,2 b1,0,2 b2,0,2
b0,1,2 b1,1,2 b2,1,2
b0,2,2 b1,2,2 b2,2,2

블록을 나타내는 아홉 줄은 각각 문자 세 개로만 이루어진다. 위에서 사이를 띄운 것은 읽기 쉽게 하려는 것이다.

$(x_1, y_1, z_1)$과 $(x_2, y_2, z_2)$는 콜로니 표면 위의 서로 다른 두 점이고, $x_1, x_2, y_1, y_2, z_1, z_2$는 $0 \le x_1, x_2, y_1, y_2, z_1, z_2 \le 3$인 정수다. $b_{i,j,k}$는 마주 보는 두 꼭짓점이 $(i, j, k)$와 $(i+1, j+1, k+1)$인 정육면체 블록이 있으면 #, 없으면 .이다. 그림 J.1A는 예제의 첫 번째 데이터셋, 그림 J.1B는 두 번째 데이터셋이다. 두 블록이 모서리나 꼭짓점에서만 닿아 있으면 케이블은 그 폭 0인 틈을 지날 수 있다. 예제의 세 번째 데이터셋인 그림 J.2A에서 가장 짧은 케이블은 점 A $(0, 0, 2)$에서 점 B $(2, 2, 2)$까지 블록 여섯 개가 공유하는 점 $(1, 1, 2)$를 지난다. 예제의 네 번째 데이터셋인 그림 J.2B에서도 가장 짧은 케이블은 서로 붙어 있지 않은 두 블록 사이의 틈을 지난다. 두 블록이 꼭짓점 하나만 공유할 때도 그 꼭짓점으로 케이블을 지나가게 할 수 있다(그림 J.2C, 예제의 다섯 번째 데이터셋).

$3 \times 3 \times 3$ 블록에서 한가운데 블록 하나만 빠진 콜로니는 주어지지 않는다.

0이 여섯 개인 줄이 입력의 끝을 나타낸다.

그림 J.2: 점선이 가장 짧은 케이블이다. 설명을 위해 일부 블록은 반투명하게 그렸다.

각 데이터셋마다 주어진 두 점을 잇는 가장 짧은 케이블의 길이를 소수점 아래 여섯째 자리까지 반올림해 한 줄에 출력한다. 소수점 아래 여섯 자리는 항상 모두 채워서 출력한다.

주어진 두 점은 언제나 케이블로 이을 수 있다. 반올림 결과가 갈리는 경계에 놓이는 답은 입력 데이터에 없다.