Moats around the Castle

Time Limit : 1 sec, Memory Limit : 65536 KB

城の堀

いま、忍者が城外から天守閣に忍び入ろうと計画を立てています。この忍者は地面を走ったり、堀の中を泳いだりすることは難なくできますが、堀から這い上がることはとても苦手なので、忍者は堀に入る回数をできるだけ少なくしたいと考えています。

お城の見取図を入力とし、城外から天守閣に至るまでに、堀から這い上がらなくてはならない最小回数を出力するプログラムを作成して下さい。お城の見取図は二次元格子として与えられます。見取り図に描かれた記号には、天守閣の位置を示す「&」と堀の位置を示す「#」の位置が記され、そのほかの地点には「.」(半角ピリオド)が記されています。なお、お城には天守閣は一つだけあるものとし、忍者は走ったり泳いだりして移動するときに東西南北方向に1マスずつ移動するものとし、斜めには移動しません。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロ2つの行で示されます。各データセットは以下の形式で与えられます。

n m
c1,1c1,2...c1,n
c2,1c2,2...c2,n
:
cm,1cm,2...cm,n

1行目に見取図の東西の幅 n と 南北の幅 m (1 ≤ n, m ≤ 100) が与えられる。続くm 行に見取り図の i 行目の情報が与えられる。各情報は記号「&」、「#」、「.」からなる長さ n の文字列である。

データセットの数は 50 を越えない。

Output

データセットごとに堀から這い上がらなくてはならない最小回数(整数)を1行に出力します。

Sample Input

5 5
.###.
#...#
#.&.#
#...#
.###.
18 15
..####....####....
####..####....####
#...............##
.#.############.##
#..#..........#.##
.#.#.########.#.##
#..#.#......#.#.##
.#.#....&...#.#.##
#..#........#.#.##
.#.#.########.#.##
#..#..........#.##
.#.############.##
#...............##
.#################
##################
9 10
#########
........#
#######.#
#.....#.#
#.###.#.#
#.#&#.#.#
#.#...#.#
#.#####.#
#.......#
#########
9 3
###...###
#.#.&.#.#
###...###
0 0

Output for the Sample Input

1
2
0
0

Source: PC Koshien 2007, Preliminary Round , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2007
http://www.pref.fukushima.jp/pc-concours/