题目描述

你有一个 $N \\times N$ 的网格棋盘。你想用 $3$ 种颜色对所有的格子进行着色，要求相邻（共边）的格子不能有相同的颜色。

你已经画了棋盘的边界。现在要确定是否能够正确地给剩下的格子着色。

具体来说，给定一个长度为 $4N-4$ 的字符串 $S$，字符串由 1、2 和 3 组成，表示从格子 $(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$ 是一个长度为 $4N-4$ 的字符串，由 1、2 和 3 组成。
• 对于 $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。大小写不限制。

样例输入 1

4
3
12312312
4
121212121212
7
321312312312121212121321
7
321312312312121312121321

样例输出 1

NO
YES
NO
YES

可以看出，在第一个和第三个测试用例中，无法正确给剩下的格子着色。第二个和第四个测试用例的正确着色如下图所示。