题目描述

$N\ \times\ N$ のマス盤面があります。 あなたは、隣接する（辺を共有する）どの二つのマスも同じ色にならないように、すべてのマスを $3$ 色で塗ろうとしています。

盤面の最も外側は、すでに塗ってしまいました。盤面の残りを意図通りに塗ることができるか判定してください。

より正確には、文字 1, 2, 3 からなる長さ $4N-4$ の文字列 $S$ が与えられます。この文字列は、盤面の最も外側のマスの色を、$(1,\ 1)$ から始めて時計回りに表します。 厳密には、$S$ の $i$ 文字目は次のマスの色を表します。

• $1\ \le\ i\ \le\ N-1$ のとき、$(1,\ i)$
• $N\ \le\ i\ \le\ 2N-2$ のとき、$(i\ -\ (N-1),\ N)$
• $2N-1\ \le\ i\ \le\ 3N-3$ のとき、$(N,\ 3N\ -\ 1\ -\ i)$
• $3N-2\ \le\ i\ \le\ 4N-4$ のとき、$(4N-2\ -\ i,\ 1)$

ここで、$(r,c)$ は $r$ 行 $c$ 列目のマスを指します。

盤面の最も外側では、隣接するどの二つのマスも同じ色でないことが保証されます。

各入力ファイルについて、$T$ 個のテストケースを解いてください。

输入格式

入力は標準入力から以下の形式で与えられる。

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

各ケースは以下の形式である。

$N$ $S$

输出格式

各テストケースについて、盤面の残りを意図通りに $3$ 色で塗る方法があれば YES と、なければ NO と出力せよ。出力中の各文字は英大文字・小文字のいずれでもよい。

题目大意

有一个 $n \times n$ 的网格图，网格最外面一圈的格子（即所有的 $(x,y),x\in \{1,n\} \lor y \in \{1,n\}$）已经被染色了，现在问你在已有的限制下网格图是否能 $3$ 染色。

每组数据输入两行，第一行是网格图的边长 $n$。

接下来的一行输入 $4 \times n -4$ 个字符，依次表示从 $(1,1)$ 按顺时针顺序的所有格子的颜色。

4
3
12312312
4
121212121212
7
321312312312121212121321
7
321312312312121312121321

NO
YES
NO
YES

提示

制約

• $1\ \le\ T\ \le\ 5\ \cdot\ 10^4$
• $3\ \le\ N\ \le\ 2\ \cdot\ 10^5$
• $S$ は文字 1, 2, 3 からなる長さ $4N-4$ の文字列である。
• $1\ \le\ i\ \le\ 4N-5$ のとき $S_i\ \neq\ S_{i+1}$ であり、また $S_{4N-4}\ \neq\ S_1$ である。
• 各入力ファイル内の $N$ の総和は $2\cdot\ 10^5$ を超えない。
• 入力中のすべての数は整数である。

Sample Explanation 1

一つ目と三つ目のテストケースでは、盤面の残りを意図通りに塗る方法がないことが示せます。二つ目と四つ目のテストケースで盤面の残りを意図通りに塗る方法を以下に示します。