AT_ndpc2026_s 2 枚の扉

縦横 $ N $ マスのグリッドがあります。上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,j) $ と表します。 辺で隣接するマスの間の状態は文字 $ c $ で表されて、 - $ c = $ `.` の時、マスの間には何もなく、自由に通行可能です。 - $ c = $ `D` の時、マスの間には扉があり、自由に通行可能です。 - $ c = $ `A` の時、マスの間には $ A $ と呼ばれる扉があり、自由に通行可能です。 - $ c = $ `B` の時、マスの間には $ B $ と呼ばれる扉があり、自由に通行可能です。 - $ c = $ `#` の時、マスの間には壁があり、通行は不可能です。 ここで 扉 $ A $ , 扉 $ B $ はグリッド上にそれぞれちょうど $ 1 $ 枚あります。 グリッド上の辺で隣接するマスの間の状態は文字列 $ 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) $ まで移動することができるグリッドの状態を **良い状態** と呼びます。 あなたは次の条件を満たすように、扉 $ A $ , 扉 $ B $ 以外の扉のうちいくつかを封鎖して通行不可能にします。 - グリッドは良い状態である。 - 追加で 扉 $ A $ , 扉 $ B $ のちょうど一方を封鎖しても、グリッドは良い状態である。 - 追加で 扉 $ A $ , 扉 $ B $ の両方を封鎖した時に、グリッドは良い状態でなくなる。 条件を満たすことは可能ですか？可能である場合は最小で何枚の扉を封鎖すれば条件を満たすかを求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースの答えを出力せよ。 各テストケースでは、条件を満たすことが可能である場合は封鎖する必要がある扉の最小枚数を、不可能である場合は `-1` を出力せよ。

### Sample Explanation 1 例えば、 $ 1 $ 番目のテストケースはすでに条件を満たしています。 ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 2 \leq N \leq 40 $ - $ S_i $ は `.`, `D`, `A`, `B`, `#` からなる長さ $ N $ の文字列 - $ T_i $ は `.`, `D`, `A`, `B`, `#` からなる長さ $ N-1 $ の文字列 - `A` と `B` は $ S_{i,j}, T_{i,j} $ の中にそれぞれちょうど $ 1 $ 回現れる - 全てのテストケースに対する $ N^2 $ の総和は $ 2 \times 10^5 $ 以下 - 全てのテストケースに対する $ N^4 $ の総和は $ 40^4 $ 以下