Carl likes to play challenging puzzle games on his phone while he is at school taking some boring class. One of his friends told him about a game called Block Mate that recently was published to the AppStore and Google Play. This game presents you with an NxM board where some squares are occupied by blocks; some of these blocks can move, while others can't. Carl can change the direction of gravity (e.g. to the right) and this will cause all blocks that can move to "fall" that direction.

For example, the first diagram below represents an initial configuration of a 4x5 board with the blocks that can move represented as 'A', and the blocks that can't move as 'B'. The diagram to the right represents the final configuration after Carl has changed the direction of gravity to the right.

---------------------           ---------------------

|   |   |   |   | B |           |   |   |   |   | B |

---------------------           ---------------------

| B | B | B |   |   |   right   | B | B | B |   |   |

---------------------   ---->   ---------------------

| A | A |   |   | A |           |   |   | A | A | A |

---------------------           ---------------------

| B | B | B |   | B |           | B | B | B |   | B |

---------------------           ---------------------

In every board there are two blocks (mates) that are, in a sense, special. One of these special blocks moves with every change in the direction of gravity, while the other remains stationary. The objective of the game is to get the first block (the one that can move) to occupy the position of the second one (stationary). In the diagrams below, the first block is represented by the symbol '-', and the second one by 'X'. Moving right and then up, we can make the first block to occupy the second one's position.

---------------------         ---------------------         ---------------------

|   |   | X |   | B |         |   |   | X |   | B |         |   |   | - | A | B |

---------------------         ---------------------         ---------------------

| B | B |   |   |   |  right  | B | B |   |   |   |   up    | B | B |   |   | A |

---------------------  ---->  ---------------------  ---->  ---------------------

| - | A |   |   | A |         |   |   | - | A | A |         |   |   |   |   |   |

---------------------         ---------------------         ---------------------

| B | B | B |   | B |         | B | B | B |   | B |         | B | B | B |   | B |

---------------------         ---------------------         ---------------------

Your task is to write a program to help Carl find the minimum sequence of changes in the direction of gravity that will solve a given board.

Notes

- It is guaranteed that there will always be a solution.

- Only the block marked as '-' can occupy the position of the one marked as 'X'. If a block with the symbol 'A' (i.e. one that moves when the direction of gravity is changed) collides with the latter, it will stop just after the collision occurs.

Input

Line 1: Two positive integers N and M (4 <= N, M <= 7) separated by a space that represent the number of rows and columns of the board, respectively.

Lines 2..2*N+2: A graphical description of the board as depicted in the diagrams above.

Output

Line 1: A single number indicating the minimum number of changes in the direction of gravity that will solve the given board.

Example

Input:
4 5
---------------------
| X |   |   |   | B |
---------------------
| B | B | B |   |   |
---------------------
| - | A |   |   | A |
---------------------
| B | B | B |   | B |
---------------------

Output:
4

In this picture, the '-' block is the blue one, and the 'X' is the red one. Notice how the sequence of steps UP, RIGHT, UP, LEFT will sove this case in the minumum number of steps.