Minimum Moves to Treasure

Problem Statement:

You are given a grid with M rows and N columns. Each cell of the grid is either a passable cell denoted by a dot (.), an obstacle denoted by a hash (#), or the treasure denoted by a capital letter T. The participant starts at the top-left corner (cell (0,0)) and must reach the treasure. You can move one step at a time in one of the four directions: up, down, left, or right.

The task is to compute the minimum number of moves required to reach the treasure. If it is impossible to reach the treasure because of obstacles, output -1.

Mathematically, if we denote the move from a cell (P) to an adjacent cell (Q) as valid (i.e., (Q) is not an obstacle and is within the boundaries of the grid), then you are to find the shortest path from (P=(0,0)) to the unique cell (T). Use the equation (moves = |i_T - 0| + |j_T - 0|) as a lower bound, where (T=(i_T,j_T)), though obstacles may cause the actual path length to be greater.

inputFormat

Input Format:

The first line contains an integer T, representing the number of test cases. For each test case, the first line contains two integers M and N, the number of rows and columns, respectively. This is followed by M lines, each containing a string of length N representing the grid. It is guaranteed that each grid contains exactly one treasure cell T.

outputFormat

Output Format:

For each test case, output a single integer on a new line representing the minimum number of moves needed for the participant to reach the treasure from the starting cell (0,0). If the treasure is unreachable, output -1.## sample

1
4 4
....
.#..
..#T
....

5