##### DWITE Online Computer Programming Contest, December 2008, Problem 5

Let's try to break out from the confines of the over-simplified 2D problems, and add some depth to the otherwise typical maze problems.

The input will contain 5 sets of data. Each set starts out with a single integer followed by lines, describing a cube space. Pound sign (`#`

) for solid space; period (`.`

) for free space; capital "A" (`A`

) for start; capital "B" (`B`

) for end.

The output will contain 5 lines – each the **shortest** distance between `A`

and `B`

in the input maze.

The maze traversal is done only though free space, in any of the 6 directions. There are no diagonal movements.

*Sample input explanation; first set:* is a empty cube, with `A`

and `B`

in two opposite corners. There are 6 different ways to get from `A`

to `B`

in 3 steps. There are also 3 different ways to get from `A`

to `B`

in 7 steps (without backtracking), but since we are looking for the *shortest* distance, the latter is of less interest.

*Sample input explanation; second set:* is also a cube, but filled space forces only a single path to be available. Think of the path this way, starting at `A`

: right, up one layer, down. Also 3 steps.

*Sample input explanation; third set:* is a cube. `A`

and `B`

are on empty layers, but they are separated by a mostly filled layer, with a single opening in its "bottom-right" corner.

#### Sample Input

```
2
A.
..
..
.B
2
A.
##
#.
#B
3
A..
...
...
###
###
##.
B..
...
...
```

#### Sample Output

```
3
3
10
```

## Comments