Taco's Shortest Path

You are given a grid representing a city. Each cell in the grid may be either walkable or blocked. Walkable cells are denoted by '.' while blocked cells by '#'. Additionally, there are two special cells: the starting position denoted by 'S' and the destination denoted by 'D'.

Your task is to find the shortest path from the starting cell to the destination cell using only one-step moves in the four cardinal directions (up, down, left, right). If the destination is unreachable, output -1.

Formally, given an \( n \times m \) grid \(G\), find the length of the shortest path from cell \(S\) to cell \(D\). The movement is allowed only between adjacent cells (up, down, left, right) and can only traverse walkable cells (i.e., cells which are not '#').

Input Format: The first line consists of an integer \( T \) indicating the number of test cases. For each test case, the first line contains two integers \( n \) and \( m \) which denote the number of rows and columns respectively. The next \( n \) lines contain \( m \) characters each representing the grid. It is guaranteed that each grid contains exactly one 'S' and one 'D'.

Output Format: For each test case, output a single integer which is the length of the shortest path or \(-1\) if no such path exists.

inputFormat

The input begins with an integer \( T \) on the first line, representing the number of test cases. Each test case is described as follows:

• The first line of each test case contains two integers \( n \) and \( m \) denoting the number of rows and columns in the grid.
• The following \( n \) lines each contain a string of length \( m \) representing the grid where characters can be S, D, ., or #.

All input is provided via standard input (stdin).

outputFormat

For each test case, output a single line with an integer representing the minimum number of moves needed to reach the destination or \(-1\) if unreachable. All output should be written to standard output (stdout).

## sample

2
4 4
S...
.##.
..#D
....
5 5
S....
#####
#####
##D##
#####

5
-1

</p>