You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.0 s

Memory Limit: 512.0 MB

Description

In the heart of SeriousLand, there lies a park shaped as an \(11 \times 11\) grid — totaling \(121\) cells. On a cloudy evening, \(9\) people were peacefully enjoying their time in the park.

Suddenly, a lightning bolt struck the area, igniting fire in some parts of the park. The fire spreads aggressively — every unit of time, it expands to the four adjacent cells: up, down, left, and right. That means if a cell \([i, j]\) is on fire at time \(T\), then the cells \([i+1, j]\), \([i-1, j]\), \([i, j+1]\), and \([i, j-1]\) will catch fire at time \(T+1\).

The screams caught the attention of SeriousLand’s only firefighter — Thakur. Equipped with a drone that can instantly drop him onto any cell in the park, Thakur immediately arrives at the scene. However, the drone can only transport Thakur himself, not the unconscious victims.

To rescue someone, Thakur must land near them, lift the unconscious person onto his shoulders, and carry them out of the park by foot, exiting the grid through any of its borders. While carrying someone, Thakur can move one cell at a time in any of the four directions (up, down, left, or right), but only through cells that are not yet consumed by fire, and each move costs one unit of time.

Unfortunately, saving all 9 people may not be possible. So, Thakur aims to rescue as many as he can before the fire reaches them. Use your programming skills for the greater good—help Thakur determine the maximum number of lives he can save.

Input

• \(11 \times 11\) grid of characters
• The character 'F' denotes fire, 'P' denotes person and '#' denotes an empty cell.

Output

• One integer : maximum number of lives thakur can save

Sample

# # # # P # F # # # # 
# # # # # F # P # # # 
# # # # # # # # # # # 
# # # # # # # # # P # 
P # # # # F # P # # # 
F # # F # F # P # # # 
# # # # # # # # # # # 
# # # # # # # # # # # 
P # # # # # # # # # # 
# # # # P # # # P # # 
# # # F # # # # # # # 

5

Thakur will save people from cell (5,1) (1,5) (9,1) (4,10) (10,9) and can not save others from fire.