Minimum Steps to Reach the Key

This problem requires you to compute the minimum number of steps needed for Joe to reach the key in a farm, which is represented as a grid. The grid consists of three types of cells:

• Free cell ('.')
• Obstacle ('#')
• Key ('K')

Joe starts at the top-left corner (cell (0,0)) and can move in four directions: up, down, left, or right. If it is impossible for Joe to reach the key, output \(-1\) (i.e., \( -1 \)).

The grid dimensions are provided as two integers \(R\) and \(C\), followed by \(R\) lines each representing a row of the farm. Use breadth-first search (BFS) to determine the minimum steps required.

inputFormat

The input is given via standard input (stdin) and follows this format:

1. The first line contains an integer \(T\) denoting the number of test cases.
2. For each test case:
• The first line contains two integers \(R\) and \(C\) separated by a space.
• Then, there are \(R\) lines each containing a string of length \(C\) representing the farm layout.

outputFormat

For each test case, output the minimum number of steps required for Joe to reach the key. If the key cannot be reached, output \(-1\). Each result should be printed on a new line to the standard output (stdout).

## sample

3
3 3
..#
#.#
..K
4 4
....
.##.
..##
...K
2 2
.#
#K

4
6
-1

</p>