配点 : $1400$ 点

問題文

$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$ 個のテストケースを解いてください。

制約

• $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$ を超えない。
• 入力中のすべての数は整数である。

入力

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

$T$

$case_1$

$case_2$

$\vdots$

$case_T$

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

$N$

$S$

出力

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

4
3
12312312
4
121212121212
7
321312312312121212121321
7
321312312312121312121321

NO
YES
NO
YES

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