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