Chess

Time Limit: 10000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2799
64-bit integer IO format: %I64d      Java class name: Main

Description

You are given a standard 8*8 chess board. There are only pawns and kings on the board. In each move, a king can move to any of its 8 neighboring cells. If you move a king into a cell occupied by a pawnn, the king will capture that pawn. You can never move a king outside the board or into a cell already occupied by another king.

Now the problem is, what is the minimal number of moves required for the kings to capture all the powns?

Input

There are multiple cases (no more than 100).

There are exactly 8 lines for each case, representing the chess board. Each line has 8 characters. The '.' character represents an empty cell, 'P' represents a cell occupied by a pawn, and 'K' represents a cell occupied by a king.

For each board, the number of kings and the number of pawn are between 1 and 10, both inclusive.

Each case is followed by an empty line.

Output

For each case, output the minimal number of moves required for the kings to capture all the powns.

Sample Input

.PPPPKP.
........
........
........
........
........
........
........

P......P
........
........
........
...KK...
........
........
P......P

.....P.P
..K....P
....K...
..PP...P
...K..KK
........
K.......
KP.K....

Sample Output

6
20
9

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .