AT_abc427_e [ABC427E] Wind Cleaning

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.

The input is given from Standard Input in the following format: > $ H $ $ W $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_H $

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

### Sample Explanation 1 Takahashi can make all trash disappear in three operations as follows: - Choose up. After this operation, trash is on cells $ (1, 1) $ and $ (2, 4) $ . - Choose right. After this operation, trash is on cell $ (1, 2) $ . - Choose up. After this operation, all trash has disappeared. ### 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} = $ `#`.