Sàn nhà là hình chữ nhật, chia thành ô. Trên đó có các ô sạch, bẩn và robot có thể dọn các ô bẩn thành ô sạch nếu nó ở ô đó. Robot có thể di chuyển qua các ô kề cạnh. Xác định số bước di chuyển ít nhất để có thể dọn sạch sàn nếu có thể.

Input

• Gồm nhiều test. Dòng đầu mỗi test là ~2~ số ~W~, ~H~ là chiểu rộng và dài của sàn nhà.
• ~H~ dòng tiếp theo, mỗi dòng chứa ~W~ ký tự miêu tả các ô của hình chữ nhật.
• Các ô của sàn có ~4~ giá trị sau:
  • .: sạch
  • *: bẩn
  • x: vật cản.
  • o: robot ~(1~ con)
• Kết thúc test là 2 số 0 0.
• Có không quá 150 test ở mỗi input.

Output

In ra số bước di chuyển ít nhất cần sử dụng. Nếu không thể làm sạch sàn, in ra ~- 1~.

Giới hạn

• ~1 \le W~, ~H \le 20~.
• Có không quá ~10~ ô bẩn trên sàn.

Sample Input

7 5
.......
.o...*.
.......
.*...*.
.......
15 13
.......x.......
...o...x....*..
.......x.......
.......x.......
.......x.......
...............
xxxxx.....xxxxx
...............
.......x.......
.......x.......
.......x.......
..*....x....*..
.......x.......
10 10
..........
..o.......
..........
..........
..........
.....xxxxx
.....x....
.....x.*..
.....x....
.....x....
0 0

Sample Output

8
49
-1