D. Skywars
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
A Skywars map

Skywars is a minigame where each player starts on a flying island and has to be the last survivor. Techno is playing a match, and now only he and 2 enemies remain. A top view of the islands shows empty points and points where island blocks exist, in such a way that the map can be represented as a grid. In order to win, Techno must reach his enemies. Therefore, he wants to know the minimum amount of blocks that must be placed so that his island and the enemies' islands are connected. Here, 2 blocks are considered connected if it is possible to move from one to the other by moving only in adjacent directions on the grid: up, down, left and right.

Input

The first line contains 2 integers, $$$N$$$ and $$$M$$$, representing the number of rows and the number of columns of the grid respectively. It is guaranteed that $$$1 \leq N,M \leq 2\cdot 10^5$$$ and that $$$N \cdot M \leq 2 \cdot 10^5$$$.

Follow $$$N$$$ lines with $$$M$$$ characters $$$c_i$$$ each. It is guaranteed that $$$c_i \in \{ T \ , \ * \ , \ . \ , \ \# \}$$$. 'T' represents where Techno is and '*' the place of the enemies. It is guaranteed that there is exactly 1 'T' and exactly 2 '*'. '.' represents cells without blocks while '$$$\#$$$' cells that have already been occupied.

Output

Print a single integer representing the minimum number of blocks needed to connect Technoblade's island to his enemies' islands.

Examples
Input
4 4
T..*
....
....
*...
Output
4
Input
4 4
*...
.T..
..*.
....
Output
2
Input
4 4
T#.*
..#.
#..#
##.*
Output
2
Input
3 3
.*.
T.*
...
Output
1
Note

Note that the cells with Techno or his enemies are not considered empty.