题目描述

李逍遥要在迷阵中寻找仙药。迷阵有M行N列，@是出发位置，*是仙药，.是安全的方格，#是不能进入的怪物方格。

每次可以向上、下、左、右移动一格，不能离开迷阵。求到达仙药需要的最少移动次数。起点不计一次移动；移动到相邻格计1次。

输入格式

输入包含多组数据。每组第一行两个整数M、N，接下来M行，每行N个字符。每组恰有一个@和一个*。输入以一行0 0结束。

输出格式

每组输出一行，表示最少移动次数。无法到达时输出-1。

样例

8 8
.@##...#
#....#.#
#.#.##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###
6 5
.*.#.
.#...
..##.
.....
.#...
....@
9 6
.#..#.
.#.*.#
.####.
..#...
..#...
..#...
..#...
#.@.##
.#..#.
0 0

10
8
-1

数据范围

1≤M,N≤20；每个输入文件至多100组数据。