You are on a mission to rescue two persons from debris of a building after an earthquake. The debris are modeled as a grid. Each cell contains a character ., #, @ or P with the following meaning:

• . represents an free cell where you can move freely
• # represents an unbreakable wall
• @ represents a pile of debris
• P represents a person that you need to save

You are currently outside of the building (grid). You want to clear debris @) so that each person can reach the outside of the building with a clear path (free of debris, containing only free cells). What is the minimum number of debris you need to clear in order to achieve this?

Input

The first line contains a two integers \(n\) and \(m\) giving the number rows and columns of grid representing the building.

The follow \(n\) lines each with a string with \(m\) characters over the alphabet ".#@P" as described above.

Constraints

• \(2 \leq n, m \leq 100\)

Output

One line with a single integer containing the minimum number of debris cells that need to be cleared so that both people have a clear path between their initial positions and the outside of the building.

We guarantee that it is always possible to clear debris in a way such that there exists a path from each person to exit the building.

Sample Test Cases

Sample input 1

Sample output 1

Sample input 2

Sample output 2

Sample input 3

Sample output 3

Sample input 4

Sample output 4