Treasure Hunt: Collect All Treasures

You are given a grid represented as an $n \times m$ matrix where each cell may contain one of the following characters:

• '0' (empty cell): You can walk through it.
• '1' (obstacle): You cannot walk through it.
• 'T' (treasure): A treasure that must be collected.
• 'S' (start): The starting point (exactly one in the grid).
• 'E' (end): The destination (exactly one in the grid).

Your task is to compute the minimum number of steps required to travel from the start 'S' to the end 'E' while collecting all treasures 'T'. You are allowed to move in the four cardinal directions (up, down, left, right). If it is impossible to do so, output $-1$.

inputFormat

The input begins with an integer $T$ denoting the number of test cases. Each test case starts with a line containing two integers $n$ and $m$ representing the number of rows and columns of the grid. This is followed by $n$ lines, each containing a string of length $m$, which describes a row of the grid.

outputFormat

For each test case, output a single line containing the minimum number of steps required to reach the destination 'E' from 'S' while collecting all treasures. If it is not possible, output $-1$.

## sample

2
5 5
S0000
010T0
01000
T0000
0000E
3 3
S1T
111
TE0

12
-1

</p>