AT_ndpc2026_s.Two doors

You are given an $N \times N$ grid. Let $(i,j)$ denote the cell in the $i$-th row from the top and the $j$-th column from the left.

The state between adjacent cells (sharing an edge) is represented by a character $c$:

• If $c =$ ., there is nothing between the cells, and you can pass freely.
• If $c =$ D, there is a door, and you can pass freely.
• If $c =$ A, there is a special door called $A$, and you can pass freely.
• If $c =$ B, there is a special door called $B$, and you can pass freely.
• If $c =$ #, there is a wall, and you cannot pass.

Here, there is exactly one door $A$ and one door $B$ in the grid.

The states between adjacent cells are given by strings $S_1, S_2, \dots, S_{N-1}$ and $T_1, T_2, \dots, T_N$:

• For $1 \leq i \leq N-1$, $1 \leq j \leq N$, the state between $(i,j)$ and $(i+1,j)$ is $S_{i,j}$.
• For $1 \leq i \leq N$, $1 \leq j \leq N-1$, the state between $(i,j)$ and $(i,j+1)$ is $T_{i,j}$.

A grid is called a good state if you can start from $(1,1)$ and reach $(N,N)$ by moving up, down, left, or right without passing through walls.

You will block some of the doors (except $A$ and $B$), making them impassable, so that the following conditions are satisfied:

• The grid is in a good state.
• Even if you additionally block exactly one of $A$ or $B$, the grid is still in a good state.
• If you additionally block both $A$ and $B$, the grid is no longer in a good state.

Is it possible to satisfy these conditions? If it is possible, find the minimum number of doors you need to block.

You are given $T$ test cases. Solve each of them.

给你一个 $N \times N$ 的网格。记 $(i,j)$ 表示从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子。

相邻格子（即共享一条边的格子）之间的状态由一个字符 $c$ 表示：

• 若 $c =$ .，则两格之间无障碍，可自由通行；
• 若 $c =$ D，则两格之间有一扇普通门，可自由通行；
• 若 $c =$ A，则两格之间有一扇特殊门 $A$，可自由通行；
• 若 $c =$ B，则两格之间有一扇特殊门 $B$，可自由通行；
• 若 $c =$ #，则两格之间有一堵墙，不可通行。

其中，整个网格中恰好存在一扇门 $A$ 和一扇门 $B$。

相邻格子之间的状态由字符串 $S_1, S_2, \dots, S_{N-1}$ 和 $T_1, T_2, \dots, T_N$ 给出：

• 对于 $1 \leq i \leq N-1$，$1 \leq j \leq N$，格子 $(i,j)$ 与 $(i+1,j)$ 之间的状态为 $S_{i,j}$；
• 对于 $1 \leq i \leq N$，$1 \leq j \leq N-1$，格子 $(i,j)$ 与 $(i,j+1)$ 之间的状态为 $T_{i,j}$。

若能从 $(1,1)$ 出发，仅通过上下左右移动（不穿过墙），到达 $(N,N)$，则称该网格处于良好状态（good state）。

你需要将部分门（但不能封锁 $A$ 和 $B$） 封锁（使其不可通行），使得满足以下全部条件：

• 网格处于良好状态；
• 在此基础上，额外封锁 $A$ 和 $B$ 中的恰好一个后，网格仍处于良好状态；
• 但在基础上，额外封锁 $A$ 和 $B$ 这两个门后，网格不再处于良好状态。

是否可能满足上述所有条件？若可能，求出所需封锁的门的最少数量。

你将收到 $T$ 组测试用例，请对每组分别求解。

The input is given from standard input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format:

$N$
$S_1$
$S_2$
$\vdots$
$S_{N-1}$
$T_1$
$T_2$
$\vdots$
$T_N$

输入从标准输入中按以下格式给出：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例按以下格式给出：

$N$
$S_1$
$S_2$
$\vdots$
$S_{N-1}$
$T_1$
$T_2$
$\vdots$
$T_N$

Print $T$ lines. On the $i$-th line, output the answer for the $i$-th test case.
For each test case, if it is possible to satisfy the conditions, output the minimum number of doors that need to be blocked; otherwise, output -1.

输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的答案。
对于每个测试用例，如果能够满足条件，则输出需要封锁的门的最少数量；否则，输出 -1。

Sample 1 Explanation:
For example, in the first test case, the conditions are already satisfied.

Constraints

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 40$
• Each $S_i$ is a string of length $N$ consisting of ., D, A, B, #
• Each $T_i$ is a string of length $N-1$ consisting of ., D, A, B, #
• A and B each appear exactly once among all $S_{i,j}$ and $T_{i,j}$
• The sum of $N^2$ over all test cases is at most $2 \times 10^5$
• The sum of $N^4$ over all test cases is at most $40^4$

样例 1 解释：
例如，在第一个测试用例中，条件已经满足。

约束条件

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 40$
• 每个 $S_i$ 是一个长度为 $N$ 的字符串，由字符 ., D, A, B, # 组成
• 每个 $T_i$ 是一个长度为 $N-1$ 的字符串，由字符 ., D, A, B, # 组成
• 在所有 $S_{i,j}$ 和 $T_{i,j}$ 中，字符 A 和 B 各恰好出现一次
• 所有测试用例中 $N^2$ 的总和不超过 $2 \times 10^5$
• 所有测试用例中 $N^4$ 的总和不超过 $40^4$