The Fairy Medicine

Problem Description

Young Li Xiaoyao's aunt is ill. Wang Xiaohu tells him to go to Fairy Spirit Island and ask the fairy for an elixir to save her. Rebellious but filial, Li Xiaoyao breaks into the island, overcomes countless dangers, and reaches its center — where he finds the elixir deep inside a maze.

The maze consists of $M \times N$ cells. Some cells contain monsters that can kill Li Xiaoyao instantly; others are safe. He wants to reach the elixir as fast as possible, so he must avoid the monster cells and pass through as few cells as possible. Help him achieve this goal.

The figure below shows a sample maze and Li Xiaoyao's route to the elixir.

Input Format

The input contains several test cases. Each test case starts with two non-zero integers $M$ and $N$, both at most $20$. $M$ is the number of rows and $N$ the number of columns. The next $M$ lines each contain $N$ characters with the following meaning:

• @: the starting position of Li Xiaoyao;

• .: a cell he can pass safely;

• #: a cell with a monster;

• *: the position of the elixir.

The input ends when a line contains two zeros.

Output Format

For each test case output one line: the minimum number of cells Li Xiaoyao must pass through to reach the elixir (counting the starting cell). If it is impossible, output $-1$.

Sample Input

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

.#..#.
.#.\*.#
.####.
..#...
..#...
..#...
..#...
#.@.##
.#..#.
0 0

Sample Output

10
8
-1

Limitation

1 s, 1024 KiB for each test case.