#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/7/problems/D

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/7/problems/D

Repovive

Kings on Diagram - Repovive Premier Round 2 | Repovive | Repovive

Repovive.

Back

Code

Upload

Submissions

Learn

7D. Kings on Diagram

2000 ptstype :zen to enter zen mode

Time: 2sMemory: 256 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$ .