A new International Common Prison for Criminals (ICPC) was built, and your old friend
Harry was moved there as a prisoner. As before, the new ICPC is one of the most secure
prisons in the world. It was designed by and old gamer and as such, the prison is not
necessarily closed, but only an incredibly logical and fast mind can get out.
The new ICPC can be represented as a grid of square cells. Each cell is empty, or it
contains a wall, a door, an opening button or a closing button. Harry was accommodated
in an empty cell, and all doors were closed. Nevertheless, Harry told you that he will
try to escape. Each time Harry is in a cell, he can move in a single step to an adjacent
cell (i.e., a cell that shares a side with his current location). Each time Harry steps on a
cell that contains an opening button, all doors open, while each time he steps on a cell
that contains a closing button, all doors close. Harry can walk around as he wants within
the prison, although he cannot move to a cell that contains a wall, neither to a cell that
contains a door if the doors are closed.
To escape from the prison, Harry needs to step outside, which means placing himself in
one of the cells on the sides and then taking one extra step out in the direction opposite
to the prison.
You obtained a map of the prison, and Harry deserves your advise. Tell him the minimum
number of steps he needs to escape, or warn him that there is no way to get out.

Input

Each test case is described using several lines. The first line contains two integers N and
M indicating respectively the number of rows and columns of the grid that represents
the prison (1 ≤ N, M ≤ 100). Line i of the next N lines describes row i of the grid
using a string of exactly M characters, where character j represents cell j of that row.
This string only contains the following characters with the indicated meanings: “H” is
the empty cell where Harry is at the beginning; “.” is an empty cell where Harry is not
at the beginning; “W” is a wall; “D” is a door; “O” is an opening button; and “C” is closing
button. You may assume that within each test case there is exactly one character “H”.
The end of input is indicated with a line containing the number −1 twice.

Output

For each test case, output a single line with a single integer representing the minimum
number of steps Harry needs to escape the prison, or the number −1 if it is impossible
for him to do so.

Example

Input: 
5 8
WWWWWWW.
WHDC...D
W.WW.WCW
W.OW..OW
.WWWWWWW
3 3
ODO
DHD
ODO
3 7
WWWWWWW
DH..OCD
WWWWWWW
4 1
W
H
O
W
1 13
HOW.DO.COW.DO
-1 -1
Output: 
21
-1
8
1
1