Robot Vacuum

You want to clean a rectangular room with a robot vacuum, and you can decide the path the robot takes yourself.

The room is divided into $1 \times 1$ square cells, and the robot vacuum is also $1 \times 1$ in size. Each cell is either clean or dirty; when the robot passes through a dirty cell, that cell becomes clean.

Some cells contain a piece of furniture of size $1 \times 1$, and the robot cannot move onto a cell that holds furniture.

In a single move the robot can go to an orthogonally adjacent cell (up, down, left, or right), and it may pass through the same cell any number of times.

Given the layout of the room, write a program that computes the minimum number of moves needed to make every dirty cell clean.

The input consists of several test cases.

The first line of each test case contains the width $w$ and the height $h$ of the room ($1 \le w, h \le 20$). The next $h$ lines describe the room, each line containing $w$ characters. Only the following four characters are used:

• . : a clean cell
• * : a dirty cell
• x : furniture
• o : the starting position of the robot vacuum

The number of dirty cells is at most $10$, and there is always exactly one robot vacuum.

The last line of the input contains two zeros separated by a space; this line is not processed.

For each test case, print on its own line the minimum number of moves required to make every dirty cell clean. If any dirty cell cannot be reached, print $-1$.