题目描述

有一个 $N\times N$ 的网格。用 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的方格。

两个共边相邻方格之间的状态用一个字符 $c$ 表示：

• .：两格之间没有障碍，可以自由通行；
• D：两格之间有一扇普通门，可以自由通行；
• A：两格之间有特殊门 A，可以自由通行；
• B：两格之间有特殊门 B，可以自由通行；
• #：两格之间有墙，无法通行。

特殊门 A 和特殊门 B 在整个网格中各恰好出现一次。

相邻方格之间的状态由字符串

给出：

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

若可以从 $(1,1)$ 出发，只经过可通行的边，通过上下左右移动到达 $(N,N)$，则称网格处于好状态。

你可以封锁若干扇普通门 D，使它们变得无法通行；不能封锁 .，也不能在这一阶段封锁特殊门 A、B。要求封锁后满足：

1. 网格仍处于好状态；
2. 无论再额外封锁特殊门 A 或特殊门 B 中的哪一扇，网格都仍处于好状态；
3. 若再额外同时封锁特殊门 A 和特殊门 B，网格将不再处于好状态。

判断能否满足这些条件。若可以，求最少需要封锁多少扇普通门；否则输出 $-1$。

共有 $T$ 组测试数据，请分别求解。

限制条件

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

输入

T
case_1
case_2
...
case_T

每组测试数据的格式如下：

N
S_1
S_2
...
S_{N-1}
T_1
T_2
...
T_N

输出

输出 $T$ 行。第 $i$ 行输出第 $i$ 组测试数据的答案。若无法满足条件，输出 $-1$。

样例输入 1

6
2
.A
.
B
2
.A
#
B
3
#D.
#BD
.A
.#
..
4
DDBD
..#D
#D.D
#DD
#DD
.A.
#.#
4
D.#D
DD#.
D.B.
#D.
.#D
...
.DA
9
DDD.D#DDD
DDDADDDDD
DD.DDDDDD
DDDD#.DDD
DD#DDDD.#
DDDDD#.#D
DD.#..DDD
DDDDD#D.D
DDD...DD
D#.D#D#D
D#DD#D.#
DDD#DD##
BDDD.D#D
DD#DDDDD
DDDDD#DD
DDD#DDDD
##DDD.#D

样例输出 1

0
-1
0
3
-1
7

例如，第一组测试数据在不封锁任何普通门时就已经满足全部条件，因此答案为 $0$。