12431243 SUSTech Online Judge
Problem 1243 --Treasure

1243: Treasure

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 67  Solved: 16
[Submit][Status][Web Board]

Description

Pisces has a treasure map showing the location of the treasure. The treasure is in a cave which can be represented as a rectangular field of \(n*m\) cells, each cell is either empty or impassable. Empty cells are marked with '.' while impassable cells are marked with '#'. Pisces can move from one empty cell to an adjacent empty cell in one unit of time. Besides, there is a magic portal in the cave, and Pisces would be transferred from one side to the other immediately if he goes there. Pisces wants to know the minimum time that he can get the treasure.

Two cells are adjacent, means there is a common edge between these two cells.

Input

The first line contains an integer \(T\) \((1\le T\le10)\), which represents the number of test cases.

In each of the test cases, the first line contains \(2\) integers \(n\) and \(m\) \((1\le n,m \le 1000)\) representing the size of the cave. In the next \(n\) lines, each line has \(m\) characters. '.' represents an empty cell, '#' represents that this cell is impassable, 'P' represents one of the two sides of the magic portal, 'T' represents the location of treasure, and 'S' represents the starting point.

Output

For each test case print one line, indicating the minimum time described above. It is guaranteed that the answer exists.

Sample Input

1
5 5
S....
...P.
#####
.....
..PT.

Sample Output

5

HINT

Source

 

[Submit][Status]