Minimum Knights Required

You are given a grid of characters with dimensions \(n \times m\). Each cell of the grid can be one of the following characters:

• K: A knight's starting position.
• .: An empty cell.
• #: An obstacle cell which cannot be passed.

Each knight can move like a king but limited to the four cardinal directions (up, down, left, right), and can only move to an adjacent cell if that cell is empty (i.e. contains a '.'). Notice that a knight starts on a cell marked with K but may only travel to neighboring cells if they are empty. The starting cell is considered reached by that knight.

Your task is to determine whether the knights placed on the grid can collectively reach every empty cell by performing a breadth-first search (BFS) from each knight. If every empty cell is reachable by at least one knight, output the total number of knights on the board; otherwise, output \(-1\).

Note: The moves allowed are up, down, left, and right (no diagonal moves). Obstacles (cells containing #) block movement.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T) 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) — the number of rows and columns of the grid, respectively. Then follow (n) lines, each containing a string of length (m), representing the grid. Each character is either 'K', '.', or '#'.

outputFormat

For each test case, output one line containing a single integer. This integer is the total number of knights on the board if all empty cells are reachable from at least one knight; otherwise, output -1.## sample

1
3 3
K.#
.#.
...

1