Code Submission Evaluation System Login

CSES - HIIT Open 2017

HIIT Open 2017

Contest start:2017-05-27 11:00:00
Contest end:2017-05-27 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard


Klotski

Time limit:1.00 s
Memory limit:512 MB

A Klotski puzzle consists of a board of size $5 \times 4$ and $10$ blocks: For example, here is one Klotski puzzle:

On each move you can choose any block and move it one step left, right, up or down. The blocks must stay inside the board, and two blocks may never overlap. It is not allowed to rotate blocks.

Your goal is to move the $2 \times 2$ block to the position from which it can escape the board. What is the minimum number of moves needed for this?

Input

The input consists of five lines, each of which contains four characters. Each character is a letter (there is a block) or a dot (empty cell).

Output

Print one integer: the minimum number of moves needed to solve the puzzle. If the puzzle is unsolvable, output $-1$.

Example

Input:
AXXC
AXXC
BEED
BGHD
F..I


Output:
116