# 2023 年上海市大学生程序设计竞赛 - 一月赛

C. Taoism follows nature

$\textbf{Because of the long statement, we will offer you a Chinese version of the statement.}$

$\textit{Taiyi religion will always be prosperous.}$

Komorebi is one of the chief apprentice of Taiyi religion, he specially loves studying tactical deployments, so he usually practices them with his younger martial brothers.

A tactical deployment can be regarded as a matrix with $n\times n$ size, everyone can stand in only one of the position of the deployment, and each position of the deployment can only contain no more than one person.

However, his younger martial brothers always forget the deployment, so Komorebi has to move them to correct place. For each operation, Komorebi can move one martial brother to adjacent empty position. Formally, if one of the martial brother is located at $(x,y)(1\leq x,y\leq n)$, there are four options that cost $1$ operation if Komorebi wants to move him:

1. If $x\gt 1$ and $(x-1,y)$ is empty, Komorebi can move him to $(x-1,y)$.

2. If $y\gt 1$ and $(x,y-1)$ is empty, Komorebi can move him to $(x,y-1)$.

3. If $x\lt n$ and $(x+1,y)$ is empty, Komorebi can move him to $(x+1,y)$.

4. If $y\lt n$ and $(x,y+1)$ is empty, Komorebi can move him to $(x,y+1)$.

One position is empty means that no person stands on it.

Besides, $\textbf{don’t forget that Komorebi is also one member in the deployment}$, so he can stand on $\textbf{any}$ empty position at $\textbf{any}$ time, this costs $0$ operation, but if he wants to move after that, he should follow the rules above and also costs $1$ operation.

They need to practice $T$ tactical deployments, for each case, Komorebi will give you the ideal deployment and the current deployment, please help Komorebi to calculate the minimum number of operations to practice each of them.

#### 以下是中文题面

$\textit{太乙长春。}$

Komorebi是太乙教的首席大弟子，他十分精于演练阵法，也乐在其中，因此他经常与师弟们一起演练阵法。

1. 如果 $x\gt 1$ 且 $(x-1,y)$ 这个格子是空的，那么就可以将他移动到$(x-1,y)$.
2. 如果 $y\gt 1$ 且 $(x,y-1)$ 这个格子是空的，那么就可以将他移动到$(x,y-1)$.
3. 如果 $x\lt n$ 且 $(x+1,y)$ 这个格子是空的，那么就可以将他移动到$(x+1,y)$.
4. 如果 $y\lt n$ 且 $(x,y+1)$ 这个格子是空的，那么就可以将他移动到$(x,y+1)$.

### 输入格式

The first line contains one integer $T$ $(1\leq T\leq 100)$, indicating the number of tactical deployments.

For the following $T$ cases, the first line of them contains one integer $n$ $(1\leq n\leq 20)$, indicating the size of the deployment, then $n$ lines contain $n$ characters indicating the ideal deployment, and then $n$ lines contain $n$ characters indicating the current deployment.

Each position of each deployment is one of the following:

’.’: indicating an empty position.

’#’: indicating a position with a person.

Notice that the ideal deployment contains Komorebi, but the current one doesn’t, so the number of ‘#’ in the current deployment equals to the number of ‘#’ in the ideal deployment $-1$.

### 输出格式

For each case, output one line contains one integer indicating the answer.

### 样例

Input
2
4
#...
....
....
...#
..#.
....
....
....
1
#
.

Output
2
0


NaN