Kings on Diagram - Repovive Premier Round 2 | Repovive

3D. Kings on Diagram

2000 pts2s256 MB

You are given an $n \times n$ board. Each cell is either empty . or contains a king K.

Your goal is to make every cell on the main diagonal contain a king, i.e. all cells $(i,i)$ for $1 \le i \le n$ , using some number of moves.

In one move, you choose one king and move it to an adjacent cell that is empty. A move from $(x,y)$ to $(x',y')$ is allowed iff:

$|x - x'| \le 1$
$|y - y'| \le 1$
$(x',y')$ is inside the board
the destination cell is empty

Compute the minimum number of moves needed, or determine that it is impossible.

Constraints

$1 \le t \le 100$
$1 \le n \le 300$
The sum of $n$ over all test cases is at most $300$
The total number of kings on the board is at least $n$
Each board row is a string of length $n$ consisting only of . and K

Input

\begin{array}{l} t \\[0.6em] \left. \begin{array}{l} n \\[0.25em] \begin{array}{l} s_{1,1}\ s_{1,2}\ \ldots\ s_{1,n} \\ s_{2,1}\ s_{2,2}\ \ldots\ s_{2,n} \\ \vdots \\ s_{n,1}\ s_{n,2}\ \ldots\ s_{n,n} \end{array} \end{array} \right\} \times t \end{array}

Each $s_{i,j}$ is a character and is either K or ..

Output

\begin{array}{l} \left. \begin{array}{l} \text{ans} \end{array} \right\} \times t \end{array}

Samples

Input

Case 1

3
K..
.KK
...

Case 2

5
K....
K....
..K.K
.....
...K.

Explanation

Case 1

Only $(3,3)$ is empty on the diagonal. Move the king from $(2,3)$ to $(3,3)$ in one move. So the answer is $1$ .

Case 2

Diagonal cells $(2,2)$ , $(4,4)$ , and $(5,5)$ are empty.

We can fill them in $3$ moves:

$(2,1)\to(2,2)$
$(3,5)\to(4,4)$
$(5,4)\to(5,5)$

At least $3$ moves are necessary because three diagonal cells are missing, and each move can place a king into at most one diagonal cell. So the answer is $3$ .

Output

Case 1

Case 2

You are given an $n \times n$ board. Each cell is either empty . or contains a king K.

Your goal is to make every cell on the main diagonal contain a king, i.e. all cells $(i,i)$ for $1 \le i \le n$ , using some number of moves.

In one move, you choose one king and move it to an adjacent cell that is empty. A move from $(x,y)$ to $(x',y')$ is allowed iff:

$|x - x'| \le 1$
$|y - y'| \le 1$
$(x',y')$ is inside the board
the destination cell is empty

Compute the minimum number of moves needed, or determine that it is impossible.

Constraints

$1 \le t \le 100$
$1 \le n \le 300$
The sum of $n$ over all test cases is at most $300$
The total number of kings on the board is at least $n$
Each board row is a string of length $n$ consisting only of . and K

\begin{array}{l} t \\[0.6em] \left. \begin{array}{l} n \\[0.25em] \begin{array}{l} s_{1,1}\ s_{1,2}\ \ldots\ s_{1,n} \\ s_{2,1}\ s_{2,2}\ \ldots\ s_{2,n} \\ \vdots \\ s_{n,1}\ s_{n,2}\ \ldots\ s_{n,n} \end{array} \end{array} \right\} \times t \end{array}

Each $s_{i,j}$ is a character and is either K or ..

\begin{array}{l} \left. \begin{array}{l} \text{ans} \end{array} \right\} \times t \end{array}

Only $(3,3)$ is empty on the diagonal. Move the king from $(2,3)$ to $(3,3)$ in one move. So the answer is $1$ .

Diagonal cells $(2,2)$ , $(4,4)$ , and $(5,5)$ are empty.

We can fill them in $3$ moves:

$(2,1)\to(2,2)$
$(3,5)\to(4,4)$
$(5,4)\to(5,5)$

At least $3$ moves are necessary because three diagonal cells are missing, and each move can place a king into at most one diagonal cell. So the answer is $3$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

3D. Kings on Diagram

Input

Output

Samples

3D. Kings on Diagram

Constraints

Input

Output

Samples

Constraints