Problem: In AD 3456, the earth is too small for hundreds of billions of people to live in peace. Interstellar Colonization Project with Cubes (ICPC) is a project that tries to move people on the earth to space colonies to ameliorate the problem. ICPC obtained funding from governments and manufactured space colonies very quickly and at low cost using prefabricated cubic blocks.

The largest colony looks like a Rubik's cube. It consists of 3 × 3 × 3 cubic blocks (Figure J.1A). Smaller colonies miss some of the blocks in the largest colony.

When we manufacture a colony with multiple cubic blocks, we begin with a single block. Then we iteratively glue a next block to existing blocks in a way that faces of them match exactly. Every pair of touched faces is glued.

<image>


Figure J.1: Example of the largest colony and a smaller colony

However, just before the first launch, we found a design flaw with the colonies. We need to add a cable to connect two points on the surface of each colony, but we cannot change the inside of the prefabricated blocks in a short time. Therefore we decided to attach a cable on the surface of each colony. If a part of the cable is not on the surface, it would be sheared off during the launch, so we have to put the whole cable on the surface. We would like to minimize the lengths of the cables due to budget constraints. The dashed line in Figure J.1B is such an example.

Write a program that, given the shape of a colony and a pair of points on its surface, calculates the length of the shortest possible cable for that colony.



Input

The input contains a series of datasets. Each dataset describes a single colony and the pair of the points for the colony in the following format.

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


(x1, y1, z1) and (x2, y2, z2) are the two distinct points on the surface of the colony, where x1, x2, y1, y2, z1, z2 are integers that satisfy 0 ≤ x1, x2, y1, y2, z1, z2 ≤ 3. bi,j,k is '#' when there is a cubic block whose two diagonal vertices are (i, j, k) and (i + 1, j + 1, k + 1), and bi,j,k is '.' if there is no block. Figure J.1A corresponds to the first dataset in the sample input, whereas Figure J.1B corresponds to the second. A cable can pass through a zero-width gap between two blocks if they are touching only on their vertices or edges. In Figure J.2A, which is the third dataset in the sample input, the shortest cable goes from the point A (0, 0, 2) to the point B (2, 2, 2), passing through (1, 1, 2), which is shared by six blocks. Similarly, in Figure J.2B (the fourth dataset in the sample input), the shortest cable goes through the gap between two blocks not glued directly. When two blocks share only a single vertex, you can put a cable through the vertex (Figure J.2C; the fifth dataset in the sample input).

You can assume that there is no colony consisting of all 3 × 3 × 3 cubes but the center cube.

Six zeros terminate the input.

<image>


Figure J.2: Dashed lines are the shortest cables. Some blocks are shown partially transparent for illustration.

Output

For each dataset, output a line containing the length of the shortest cable that connects the two given points. We accept errors less than 0.0001. You can assume that given two points can be connected by a cable.

Examples

Input

0 0 0 3 3 3
###
###
###
###
###
###
###
###
###
3 3 0 0 0 3
#..
###
###
###
###
###
#.#
###
###
0 0 2 2 2 2
...
...
...
.#.
#..
...
##.
##.
...
0 1 2 2 1 1
...
...
...
.#.
#..
...
##.
##.
...
3 2 0 2 3 2
###
..#
...
..#
...
.#.
..#
..#
.##
0 0 0 0 0 0


Output

6.70820393249936941515
6.47870866461907457534
2.82842712474619029095
2.23606797749978980505
2.82842712474619029095


Input

0 0 0 3 3 3









3 3 0 0 0 3
..





.#


0 0 2 2 2 2
...
...
...
.#.
..
...
.
.
...
0 1 2 2 1 1
...
...
...
.#.
..
...
.
.
...
3 2 0 2 3 2

..#
...
..#
...
.#.
..#
..#
.##
0 0 0 0 0 0


Output

6.70820393249936941515
6.47870866461907457534
2.82842712474619029095
2.23606797749978980505
2.82842712474619029095

Solution (in CPP):

Solution:
#include <stdio.h>
#include <math.h>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

struct point{
  int x, y, z;
  point(int x_, int y_, int z_) : x(x_), y(y_), z(z_) {}
  bool operator< (const point& rhs) const {
    return false;
  }
};

const int dv = 18;
const int sd = 420;

int b[5][5][5];
int dvs[dv + 1] = {0, 60, 70, 84, 105, 120, 140, 168, 180, 210, 240, 252, 280, 300, 315, 336, 350, 360};
int rot[dv * 4 + 1][2];

int xtov[dv * 3 + 1];

vector<point> ed[dv * 3 + 1][dv * 3 + 1][dv * 3 + 1];
priority_queue< pair<double, point> > pq;
bool vis[dv * 3 + 1][dv * 3 + 1][dv * 3 + 1];

double dist(int xa, int ya, int za, int xb, int yb, int zb){
  int dx = xa - xb, dy = ya - yb, dz = za - zb;
  double d = sqrt(dx * dx + dy * dy + dz * dz);
  return d;
}

int main(){
  int i, j, k;
  for(i = 0; i <= dv * 3 + 1; i++){
    if(i < dv) xtov[i] = dvs[i];
    else xtov[i] = xtov[i - dv] + sd;
  }
  for(i = 0; i < dv; i++){
    rot[i][0] = i;
    rot[i][1] = 0;
    rot[dv + i][0] = dv;
    rot[dv + i][1] = i;
    rot[2 * dv + i][0] = dv - i;
    rot[2 * dv + i][1] = dv;
    rot[3 * dv + i][0] = 0;
    rot[3 * dv + i][1] = dv - i;
  }

  for(;;){
    int x1, y1, z1;
    int x2, y2, z2;
    scanf("%d%d%d", &x1, &y1, &z1);
    scanf("%d%d%d", &x2, &y2, &z2);
    if(x1 == 0 && y1 == 0 && z1 == 0
        && x2 == 0 && y2 == 0 && z2 == 0) break;

    for(i = 0; i <= 3 * dv; i++){
      for(j = 0; j <= 3 * dv; j++){
        for(k = 0; k <= 3 * dv; k++){
          ed[i][j][k].clear();
          vis[i][j][k] = false;
        }
      }
    }
    while(!pq.empty()) pq.pop();

    char tmp[5];
    for(i = 0; i < 3; i++){
      for(j = 0; j < 3; j++){
        scanf("%s", tmp);
        for(k = 0; k < 3; k++){
          b[k][j][i] = (tmp[k] == '#');
        }
      }
    }

    for(i = 0; i <= 3; i++){
      for(j = 0; j <= 3; j++){
        for(k = 0; k <= 3; k++){
          // (i, j, k) (i + 1, j, k) (i, j + 1, k) (i + 1, j + 1, k)
          // square (i, j, k - 1), (i, j, k)
          if(i < 3 && j < 3 && (k == 0 ? 0 : b[i][j][k - 1]) + b[i][j][k] == 1){
            for(int l0 = 0; l0 < 4 * dv; l0++){
              for(int l1 = l0 + 1; l1 < 4 * dv; l1++){
                // (i * dv + rot[l][0], j * dv + rot[l][1], k * dv)
                int nx0 = i * dv + rot[l0][0], ny0 = j * dv + rot[l0][1], nz0 = k * dv;
                int nx1 = i * dv + rot[l1][0], ny1 = j * dv + rot[l1][1], nz1 = k * dv;
                ed[nx0][ny0][nz0].push_back(point(nx1, ny1, nz1));
                ed[nx1][ny1][nz1].push_back(point(nx0, ny0, nz0));
              }
            }
          }
          // (i, j, k) (i + 1, j, k) (i, j, k + 1) (i + 1, j, k + 1)
          // square (i, j - 1, k), (i, j, k)
          if(i < 3 && k < 3 && (j == 0 ? 0 : b[i][j - 1][k]) + b[i][j][k] == 1){
            for(int l0 = 0; l0 < 4 * dv; l0++){
              for(int l1 = l0 + 1; l1 < 4 * dv; l1++){
                // (i * dv + rot[l][0], j * dv, k * dv + rot[l][1])
                int nx0 = i * dv + rot[l0][0], ny0 = j * dv, nz0 = k * dv + rot[l0][1];
                int nx1 = i * dv + rot[l1][0], ny1 = j * dv, nz1 = k * dv + rot[l1][1];
                ed[nx0][ny0][nz0].push_back(point(nx1, ny1, nz1));
                ed[nx1][ny1][nz1].push_back(point(nx0, ny0, nz0));
              }
            }
          }
          // (i, j, k) (i, j + 1, k) (i, j, k + 1) (i, j + 1, k + 1)
          // square (i - 1, j, k), (i, j, k)
          if(j < 3 && k < 3 && (i == 0 ? 0 : b[i - 1][j][k]) + b[i][j][k] == 1){
            for(int l0 = 0; l0 < 4 * dv; l0++){
              for(int l1 = l0 + 1; l1 < 4 * dv; l1++){
                // (i * dv, j * dv + rot[l][0], k * dv + rot[l][1])
                int nx0 = i * dv, ny0 = j * dv + rot[l0][0], nz0 = k * dv + rot[l0][1];
                int nx1 = i * dv, ny1 = j * dv + rot[l1][0], nz1 = k * dv + rot[l1][1];
                ed[nx0][ny0][nz0].push_back(point(nx1, ny1, nz1));
                ed[nx1][ny1][nz1].push_back(point(nx0, ny0, nz0));
              }
            }
          }
        }
      }
    }

    pq.push(make_pair(0.0, point(x1 * dv, y1 * dv, z1 * dv)));
    double ans = 0.0;

    while(!pq.empty()){
      double nd = pq.top().first;
      int nx = pq.top().second.x, ny = pq.top().second.y, nz = pq.top().second.z;
      pq.pop();

      if(vis[nx][ny][nz]) continue;
      vis[nx][ny][nz] = true;

      if(nx == x2 * dv && ny == y2 * dv && nz == z2 * dv){
        ans = nd;
        break;
      }

      for(point pp : ed[nx][ny][nz]){
        if(!vis[pp.x][pp.y][pp.z]){
          pq.push(make_pair(nd - dist(xtov[nx], xtov[ny], xtov[nz], xtov[pp.x], xtov[pp.y], xtov[pp.z]), pp));
        }
      }
    }
    printf("%.20lf\n", -ans / sd);
  }
  return 0;
}