Дан цикл с $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$;
  • Для каждого $0 \le x \le y \le m - 1$, удовлетворяющего условию $x + y = 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$) — количество вершин в цикле.

Вторая строка содержит строку $c$ длины $n$ ($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 \overset{\text{R}}{\leftrightarrow} 1 \overset{\text{B}}{\leftrightarrow} 2 \overset{\text{B}}{\leftrightarrow} 3 \overset{\text{R}}{\leftrightarrow} 4 \overset{\text{B}}{\leftrightarrow} 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)$, палиндромного пути не существует.