Moving a Log

Logging is done on a square field. The field is described with characters: 0 is an empty cell, 1 is an uncut tree, B is the initial position of the log, and E is the final position where the log must be moved.

A field may look like this.

B 0 0 1 1B 0 0 0 0B 0 0 0 01 1 0 0 0E E E 0 0

The log always has length 3, and its three cells are consecutive in one row or one column. The initial three cells are marked with B, and the target three cells are marked with E. The log can use only the following five basic actions.

When the log moves up, down, left, or right, all three cells occupied after the move must remain inside the field, and none of them may contain 1. Each move shifts the log by exactly one cell, and the log must always stay on a single row or a single column.

A rotation is performed only around the middle cell of the log. Because the length is 3, that center cell always exists. To rotate, the entire 3 x 3 square around the center cell must be inside the field, and none of those 9 cells may contain 1. In the diagrams below, every cell marked with a question mark must also be empty.

Space needed to rotate a horizontal log:

0 0 0 0 00 ? ? ? 00 B B B 00 ? ? ? 00 0 0 0 0

Space needed to rotate a vertical log:

0 0 0 0 00 ? B ? 00 ? B ? 00 ? B ? 00 0 0 0 0

Find the minimum number of basic actions needed to move the log from its initial position to its final position.

The first line contains N, the side length of the square field. (4 <= N <= 50)

The next N lines describe the field. Each line is a string of length N with no spaces between characters. Each character is one of 0, 1, B, and E.

There are exactly three B cells for the initial position and exactly three E cells for the final position. Each group of three cells is consecutive in one row or one column.

Print the minimum number of actions needed to move the log from its initial position to its final position.

If it is impossible, print 0.