Problem D: Dr. Nakamura's Lab.

Dr.中村は偉大な発明者である, 今日も常人には発想出来ない新たな発明に取り掛かっている. 今発明しているのは新たな防犯システムとコンテナである.

防犯システムの方は上に乗った者を識別して招かれざる客だった場合, 電流を流して気絶させるパネルである. このパネルは踏まないように上を通過しても無駄で, 空中のものに対し放電する. しかし, まだ完成には程遠く, 電流は強すぎて調節が不可能で, 一度放電すると充電しない限り使えない. また, 人と物体の区別ができず, そもそも人自体区別できない等欠点をあげればキリがない.

コンテナの方は謎の力によって常時地面から浮いており, 運ぶのに便利に作ってある. しかし, これも完成には遠く, 一度押すと何かにぶつかるまで止まらない.

Dr.中村は一日の作業を終え, 帰宅しようとしたが未完成のパネルを設置したままだということに気づいた. これを取り外すのは防犯上非常に困難に作ってある上に, これを通らなければ帰れないような位置に設置してしまったのでDr.中村は途方に暮れた. しかし, 素晴らしい頭脳を持つDr.中村は解決案をすぐに思いついた. パネルは一度放電させれば通れるようになるため, コンテナを通過させればパネルの上を通れるようになる, そう考えた. 実際, パネルの上にコンテナを通過させると, コンテナは電流によって消滅してしまう一方でパネルは放電し, 通れるようになる.

しかし, 研究室の中は入り組んでおり, うまくコンテナを動かさないとパネルを通過させられない. Dr.中村は助手であるあなたにメールで助けを求めた. あなたの仕事は研究室の情報が与えられた時にDr.中村が出口までたどり着くためのプログラムを作成することである.

研究室は二次元グリッドで与えられ, Dr.中村は一度の移動で上下左右に隣接するセルに移動することが出来る.ただし, 障害物, コンテナ, 放電していないパネルのセルには移動できない.

Dr.中村は上下左右に隣接するセルにあるコンテナを押すことができ, コンテナはDr.中村がいる方向と逆の方向に別のコンテナか障害物にぶつかる, あるいは放電されていないパネルの上を通過するまで動く. また, 何かにぶつかり止まった場合, ぶつかる直前のセルで静止する.

出口はコンテナもDr.中村も侵入可能である. コンテナは出口を通っても消滅せず、そのまま通過する.

壁にぶつかって出口をふさぐことはある. この場合は出口に進入できない.

あなたのプログラムが要求されていることは, Dr.中村は最少何回の移動で研究室を脱出できるかを出力することのみである. なぜなら, Dr.中村は素晴らしい頭脳の持ち主なのでそれさえわかれば自分で脱出するからである.

Input

入力は複数のデータセットからなり, 一行目に研究室の縦の長さ H と横の長さ W が与えられる. 2行目以降では研究室の状態が H × W 個の文字で表わされる. 各文字が表すものは以下のとおりである:

縦と横の長さがともに 0 のとき入力の終了を表す. これについて処理をする必要はない.

以下のことを仮定してよい.

Output

各データセットについて最少の移動回数を１行に出力せよ. なお、Dr.中村が脱出できない場合、”-1”と出力せよ.

Sample Input

5 5
#####
##@##
#wc.#
#Ew.#
#####
5 5
#####
##@.#
#wc.#
#E#.#
#####
3 6
######
#@.wE#
######
0 0

Output for the Sample Input

3
5
-1