题目描述

有一个 $N \times N$ 的方格棋盘。你需要用三种颜色给所有格子染色，要求任意相邻（共享边）的两个格子颜色不同。

棋盘最外层的格子已经被染色。请判断是否可以按照要求给剩下的格子染色。

更准确地说，给定一个由字符 1、2、3 组成的长度为 $4N-4$ 的字符串 $S$，该字符串表示从 $(1, 1)$ 开始，按顺时针顺序记录的最外层格子的颜色。具体地，第 $i$ 个字符表示如下格子的颜色：

• 当 $1 \leq i \leq N-1$ 时，对应 $(1, i)$；
• 当 $N \leq i \leq 2N-2$ 时，对应 $(i - (N-1), N)$；
• 当 $2N-1 \leq i \leq 3N-3$ 时，对应 $(N, 3N-1-i)$；
• 当 $3N-2 \leq i \leq 4N-4$ 时，对应 $(4N-2-i, 1)$。

其中，$(r, c)$ 表示第 $r$ 行第 $c$ 列的格子。

保证最外层格子中，任意相邻的两个格子颜色不同。

对于每个输入文件，请判断是否存在一种方案，可以用三种颜色给剩下的格子染色，使得任意相邻格子颜色不同。

输入格式

输入从标准输入读入，格式如下：

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

每个测试用例格式如下：

$N$ $S$

输出格式

对于每个测试用例，如果存在一种方案可以按照要求用三种颜色染色，则输出 YES，否则输出 NO。输出时不区分大小写。

样例 1

输入

4
3
12312312
4
121212121212
7
321312312312121212121321
7
321312312312121312121321

输出

NO
YES
NO
YES

说明/提示

限制

• $1 \leq T \leq 5 \cdot 10^4$
• $3 \leq N \leq 2 \cdot 10^5$
• $S$ 是由字符 1、2、3 组成的长度为 $4N-4$ 的字符串。
• 对于 $1 \leq i \leq 4N-5$，有 $S_i \neq S_{i+1}$，且 $S_{4N-4} \neq S_1$。
• 每个输入文件中所有 $N$ 的总和不超过 $2 \cdot 10^5$。
• 输入中的所有数字均为整数。

样例解释 1

对于第一个和第三个测试用例，可以证明无法按照要求染色。对于第二个和第四个测试用例，下面给出了可以按照要求染色的方案。

由 ChatGPT 4.1 翻译