Very Important Pig (VIP) is an interesting game played on an n × m grid.

There are 4 types of cells in the grid: empty(“.”), dirt(“*”), ladder(“#”) and rock(“@”).

Our VIP(“P”) is running according to following rules:

• If the VIP is on a ladder:
  • He will move to the right cell if it’s empty or a ladder.
  • Or move to the top cell if it’s empty or a ladder. He won’t do this if the right cell is empty or a ladder.
  • Otherwise, the VIP will stay where he was.
• If the VIP is NOT on a ladder:
  • He will fall into the below cell if it’s empty.
  • Or move to the right cell if it’s empty or a ladder. He won’t do this if the below cell is empty.
  • Otherwise, the VIP will stay where he was.

The goal of game is to help our VIP go back home(“H”) by digging the dirt. A dirt cell becomes empty after digging, and rocks can’t be destroyed. Your task is to dig the minimum number of cells to achieve the goal.

The input consists of multiple test cases. Each case begins with two integers n and m, indicating height and width of the grid. The next n lines each contains m characters, describing the game map. The characters might be “.”, “*”, “#”, “@”, “P” and “H”, which are explained above. You may assume VIP’s initial position(“P”) and home(“H”) are in empty cells, and there’s exactly one “P” and one “H” in the map. (2 ≤ n,m ≤ 1000)

The input ends with n=m=0.

For each test case, output the minimum number of cells to be dug after “Case x: ”, where x is the case number. If it is impossible to accomplish the game, output “oops” instead.

1 3
P*H
3 5
*#@.H
*#**#
P#***
4 6
P@*#.*
*@#@.H
*@#@.#
*.#@.#
4 5
P....
****@
#*#..
****H
1 2
HP
2 3
@H*
P#.
2 3
@H*
P#*
0 0

Case 1: 1
Case 2: 2
Case 3: 4
Case 4: 1
Case 5: oops
Case 6: oops
Case 7: 0

Following figure shows VIP’s path(“o”) in case 2:

*#@.o
*oooo
oo***