Dany jest cykl o $n$ wierzchołkach ponumerowanych od $0$ do $n - 1$. Dla każdego $0 \le i \le n - 1$ istnieje nieskierowana krawędź między wierzchołkiem $i$ a wierzchołkiem $((i + 1) \pmod n)$ o kolorze $c_i$ ($c_i = \text{R}$ lub $\text{B}$).

Określ, czy poniższy warunek jest spełniony dla każdej pary wierzchołków $(i, j)$ ($0 \le i < j \le n - 1$):

• Istnieje ścieżka palindromowa między wierzchołkiem $i$ a wierzchołkiem $j$. Zauważ, że ścieżka nie musi być prosta. Formalnie, musi istnieć ciąg $p = [p_0, p_1, p_2, \dots, p_m]$ taki, że:
  • $p_0 = i, p_m = j$;
  • Dla każdego $0 \le x \le m - 1$, zachodzi $p_{x+1} = (p_x + 1) \pmod n$ lub $p_{x+1} = (p_x - 1) \pmod n$;
  • Dla każdego $0 \le x \le y \le m - 1$ spełniającego $x + y = m - 1$, krawędź między $p_x$ a $p_{x+1}$ ma ten sam kolor co krawędź między $p_y$ a $p_{y+1}$.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwsza linia zawiera liczbę przypadków testowych $t$ ($1 \le t \le 10^5$) — liczbę przypadków testowych. Następnie opisano przypadki testowe.

Pierwsza linia każdego przypadku testowego zawiera liczbę całkowitą $n$ ($3 \le n \le 10^6$) — liczbę wierzchołków w cyklu.

Druga linia zawiera ciąg $c$ o długości $n$ ($c_i = \text{R}$ lub $\text{B}$) — kolor każdej krawędzi.

Gwarantuje się, że suma $n$ we wszystkich przypadkach testowych nie przekracza $10^6$.

Wyjście

Dla każdego przypadku testowego wypisz „YES” (bez cudzysłowów), jeśli istnieje ścieżka palindromowa między każdą parą wierzchołków, a w przeciwnym razie wypisz „NO” (bez cudzysłowów).

Odpowiedź można wypisać w dowolnej wielkości liter. Na przykład ciągi „yEs”, „yes”, „Yes” oraz „YES” zostaną uznane za odpowiedzi pozytywne.

Przykład

Wejście 1

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

Wyjście 1

YES
YES
YES
NO
NO
YES
NO

Uwagi

W pierwszym przypadku testowym łatwo pokazać, że istnieje ścieżka palindromowa między dowolnymi dwoma wierzchołkami.

W drugim przypadku testowym, dla dowolnych dwóch wierzchołków, istnieje ścieżka palindromowa złożona tylko z czerwonych krawędzi.

W trzecim przypadku testowym cykl wygląda następująco: $0 \xrightarrow{\text{R}} 1 \xrightarrow{\text{B}} 2 \xrightarrow{\text{B}} 3 \xrightarrow{\text{R}} 4 \xrightarrow{\text{B}} 0$. Przyjmując $(i, j) = (0, 3)$ jako przykład, ścieżka $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$ jest ścieżką palindromową. Zatem warunek jest spełniony dla $(i, j) = (0, 3)$.

W czwartym przypadku testowym, dla $(i, j) = (0, 2)$, nie istnieje ścieżka palindromowa.