Bombed Maze

You are given an n × n grid that contains five characters: P, K, ., X, and #. Their meanings are as follows:

• P is the starting point.
• K is the destination.
• . represents a traversable road.
• X represents a rock wall which cannot be passed and is not affected by explosions.
• # represents a brick wall which cannot be passed unless it is destroyed by an explosion.

You also have one bomb. You may place the bomb on any cell that is not a rock wall (X). When the bomb detonates, it clears (i.e. turns to an empty cell .) the cell where it is placed and then the explosion propagates in the four cardinal directions – up, down, left, and right – until it either meets a rock wall or goes out of bounds. Note: Even if the explosion passes over the starting point P or the destination K, their positions are preserved.

After the explosion, you are to compute the length of the shortest path from P to K on the modified grid. If no valid path exists, output -1. You are allowed to choose the bomb placement optimally to minimize the path length.

The explosion pattern in each of the four directions is given by the following formula (in LaTeX):

$$\text{For a bomb placed at }(i,j),\text{ for each direction }(\Delta i,\Delta j), \quad \text{it clears }(i+k\Delta i, j+k\Delta j) \quad \text{for } k \ge 0 \text{ until } (i+k\Delta i, j+k\Delta j) \text{ is out of bounds or is a rock wall (}X\text{)}. $$

inputFormat

The first line contains an integer n (the size of the grid).

Then n lines follow, each containing a string of length n composed of the characters P, K, ., X, and #.

outputFormat

Output a single integer representing the length of the shortest path from P to K after you have optimally placed and detonated the bomb. If no path exists, output -1.

sample

3
P#K
###
###

2