A Freshman Needs Friends

Interview

Time limit1sMemory limit1024 MB

Summary

Given an N by M grid with walls, Doyeon's start cell, and people, count how many people are reachable from her by moving up, down, left, or right.

Level: Easy3 of 10
Topics: BFS, Graph, Array, Queue
Solved: No attempts yet

Problem

Doyeon is a freshman who entered university in 2020. Because of remote classes she could not go to campus, so she had no friends there. Now that in-person classes have finally begun, she wants to get close to the people on campus as soon as possible.

The campus of Doyeon's university is $N \times M$ in size, and movement on campus is up, down, left, or right onto a cell that is not a wall. For example, if Doyeon is at ( $x$ , $y$ ), she can move to ( $x+1$ , $y$ ), ( $x$ , $y+1$ ), ( $x-1$ , $y$ ), or ( $x$ , $y-1$ ). She cannot move outside the campus.

For poor Doyeon, write a program that prints the number of people she can meet on campus.

Input

The first line gives two integers $N$ ( $1 \leq N \leq 600$ ) and $M$ ( $1 \leq M \leq 600$ ), the size of the campus.

From the second line, $N$ lines give the campus information. O is an empty space, X is a wall, I is Doyeon, and P is a person. It is guaranteed that I is given exactly once.

Output

On the first line, print the number of people Doyeon can meet. If she meets nobody, print TT.

Examples2

Example 1
Input
```
3 5
OOOPO
OIOOX
OOOXP
```
Expected output
```
1
```
Example 2
Input
```
3 3
IOX
OXP
XPP
```
Expected output
```
TT
```