Se te da un ciclo con $n$ vértices numerados del $0$ al $n - 1$. Para cada $0 \le i \le n - 1$, existe una arista no dirigida entre el vértice $i$ y el vértice $((i + 1) \pmod n)$ con el color $c_i$ ($c_i = \text{R}$ o $\text{B}$).

Determina si la siguiente condición se cumple para cada par de vértices $(i, j)$ ($0 \le i < j \le n - 1$):

• Existe una ruta palíndromo entre el vértice $i$ y el vértice $j$. Ten en cuenta que la ruta puede no ser simple. Formalmente, debe existir una secuencia $p = [p_0, p_1, p_2, \dots, p_m]$ tal que:
  • $p_0 = i, p_m = j$;
  • Para cada $0 \le x \le m - 1$, se cumple que $p_{x+1} = (p_x + 1) \pmod n$ o $p_{x+1} = (p_x - 1) \pmod n$;
  • Para cada $0 \le x \le y \le m - 1$ que satisface $x + y = m - 1$, la arista entre $p_x$ y $p_{x+1}$ tiene el mismo color que la arista entre $p_y$ y $p_{y+1}$.

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $t$ ($1 \le t \le 10^5$) — el número de casos de prueba. A continuación, se describen los casos de prueba.

La primera línea de cada caso de prueba contiene un entero $n$ ($3 \le n \le 10^6$) — el número de vértices en el ciclo.

La segunda línea contiene una cadena $c$ de longitud $n$ ($c_i = \text{R}$ o $\text{B}$) — el color de cada arista.

Se garantiza que la suma de $n$ sobre todos los casos de prueba no excede $10^6$.

Salida

Para cada caso de prueba, imprime "YES" (sin comillas) si existe una ruta palíndromo entre cualquier par de nodos, y "NO" (sin comillas) en caso contrario.

Puedes imprimir la respuesta en cualquier formato (mayúsculas o minúsculas). Por ejemplo, las cadenas "yEs", "yes", "Yes" y "YES" serán reconocidas como respuestas positivas.

Ejemplos

Entrada 1

7
5
RRRRR
5
RRRRB
5
RBBRB
6
RBRBRB
6
RRBBRB
5
RBRBR
12
RRBRRBRRBRRB

Salida 1

YES
YES
YES
NO
NO
YES
NO

Nota

En el primer caso de prueba, es fácil demostrar que existe una ruta palíndromo entre cualesquiera dos vértices.

En el segundo caso de prueba, para cualesquiera dos vértices, existe una ruta palíndromo con solo aristas rojas.

En el tercer caso de prueba, el ciclo es el siguiente:

Tomando $(i, j) = (0, 3)$ como ejemplo, entonces $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$ es una ruta palíndromo. Por lo tanto, la condición se cumple para $(i, j) = (0, 3)$.

En el cuarto caso de prueba, cuando $(i, j) = (0, 2)$, no existe una ruta palíndromo.