Block Game

Bud bought a new board game and is hooked. He has played it over and over, and he believes he can solve any board in the minimum number of moves, but he is not sure. He wants a program that computes the minimum number of moves needed to solve different boards, so he can double-check his answers.

You are given a $6 \times 6$ board and a set of pieces: $2 \times 1$ or $3 \times 1$ (vertical) pieces and $1 \times 2$ or $1 \times 3$ (horizontal) pieces. Horizontal pieces slide horizontally only, and vertical pieces slide vertically only. A piece may be slid only if no other piece and no wall obstructs its path.

There is one special $1 \times 2$ horizontal piece. There is also a gap in the wall on the right side, on the same row as the special piece, through which only the special piece can fit. The goal is to get that special horizontal piece out through the gap on the right side.

Sliding a piece any number of squares counts as one move. (That is, sliding a piece one square is one move, and sliding it two squares at once is also one move.)

The input contains several test cases. Each test case begins with a line containing a single capital letter, indicating the special piece that must be moved off the board. The next 6 lines each contain 6 characters. Each character is either a . (period), indicating an empty square, or a capital letter, indicating part of a piece. The letters are guaranteed to form pieces of size $1 \times 2$, $1 \times 3$, $2 \times 1$, or $3 \times 1$, and no letter represents more than one piece on any given board. The letter indicating the special piece is guaranteed to correspond to a $1 \times 2$ piece somewhere on the board. The end of the data is indicated by a line containing a single * (asterisk).

For each test case, print a single integer: the smallest number of moves needed to remove the given special piece, or -1 if it is not possible. Print each integer on its own line, with no blank lines between answers.