给定一个包含 $n$ 个顶点的环，顶点编号为 $0$ 到 $n-1$。对于每个 $0 \le i \le n-1$，顶点 $i$ 和顶点 $((i + 1) \pmod n)$ 之间存在一条颜色为 $c_i$（$c_i = \text{R}$ 或 $\text{B}$）的无向边。
确定对于每一对顶点 $(i, j)$（$0 \le i < j \le n-1$），以下条件是否成立：
- 顶点 $i$ 和顶点 $j$ 之间存在一条回文路径。注意，该路径不一定是简单路径。形式化地，必须存在一个序列 $p = [p_0, p_1, p_2, \dots, p_m]$ 使得：
- $p_0 = i, p_m = j$；
- 对于每个 $0 \le x \le m - 1$，满足 $p_{x+1} = (p_x + 1) \pmod n$ 或 $p_{x+1} = (p_x - 1) \pmod n$；
- 对于每个满足 $x + y = m - 1$ 的 $0 \le x \le y \le m - 1$，连接 $p_x$ 和 $p_{x+1}$ 的边的颜色与连接 $p_y$ 和 $p_{y+1}$ 的边的颜色相同。
输入格式
每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^5$)。接下来是各测试用例的描述。
每个测试用例的第一行包含一个整数 $n$ ($3 \le n \le 10^6$)，表示环中的顶点数。
第二行包含一个长度为 $n$ 的字符串 $c$ ($c_i = \text{R}$ 或 $\text{B}$)，表示每条边的颜色。
保证所有测试用例的 $n$ 之和不超过 $10^6$。
输出格式
对于每个测试用例，如果任意一对节点之间都存在回文路径，则打印 “YES”（不含引号），否则打印 “NO”（不含引号）。
你可以以任何大小写形式输出答案。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 都将被识别为肯定回答。
样例
输入格式 1
7 5 RRRRR 5 RRRRB 5 RBBRB 6 RBRBRB 6 RRBBRB 5 RBRBR 12 RRBRRBRRBRRB
输出格式 1
YES YES YES NO NO YES NO
说明
在第一个测试用例中，很容易证明任意两个顶点之间都存在回文路径。
在第二个测试用例中，对于任意两个顶点，都存在一条仅由红色边组成的回文路径。
在第三个测试用例中，环的结构如下：$0 \xrightarrow{\text{R}} 1 \xrightarrow{\text{B}} 2 \xrightarrow{\text{B}} 3 \xrightarrow{\text{R}} 4 \xrightarrow{\text{B}} 0$。以 $(i, j) = (0, 3)$ 为例，路径 $0 \xrightarrow{\text{R}} 1 \xrightarrow{\text{B}} 2 \xrightarrow{\text{B}} 3 \xrightarrow{\text{R}} 4 \xrightarrow{\text{B}} 0 \xrightarrow{\text{B}} 4 \xrightarrow{\text{R}} 3$ 是一条回文路径。因此，该条件对于 $(i, j) = (0, 3)$ 成立。
在第四个测试用例中，当 $(i, j) = (0, 2)$ 时，不存在回文路径。