Problem Statement

There is a grid with $H$ rows and $W$ columns. Let $(i, j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left.

Takahashi is on one of the cells in this grid, and there is trash on some cells of the grid.

The states of the cells are given by $H$ strings $S_1, S_2, \ldots, S_H$ of length $W$, where $S_{i, j}$ denotes the $j$-th character of $S_i$ and represents the following state:

• If $S_{i, j} =$ T, cell $(i, j)$ is the cell where Takahashi is.
• If $S_{i, j} =$ #, cell $(i, j)$ is a cell with trash.
• If $S_{i, j} =$ ., cell $(i, j)$ is an empty cell without trash.

There is no trash on the cell where Takahashi is.

He can repeatedly perform the following operation:

• Choose one of the four directions (up, down, left, or right), and move all trash simultaneously one cell in that direction. Here, if trash goes outside the grid, the trash disappears, and if trash moves to the cell where he is, he gets dirty.

Determine whether it is possible for him to make all trash disappear without getting dirty, and if possible, find the minimum possible number of operations.

Constraints

• $2 \leq H, W \leq 12$
• $S_i$ is a string of length $W$ consisting of T, #, and ..
• There is exactly one $(i, j)$ such that $S_{i, j} =$ T.
• There is at least one $(i, j)$ such that $S_{i, j} =$ #.

Input

The input is given from Standard Input in the following format:

H W
S_1
S_2
\vdots
S_H

Output

If it is possible for Takahashi to make all trash disappear without getting dirty, print the minimum possible number of operations. Otherwise, print -1.