C. Найти и заменить
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$s$$$, состоящая из строчных латинских букв. За одну операцию можно выбрать символ и заменить все вхождения этого символа на $$$\texttt{0}$$$, или заменить все вхождения этого символа на $$$\texttt{1}$$$.

Можно ли выполнить некоторое количество ходов так, чтобы в результате получилась чередующаяся бинарная строка$$$^{\dagger}$$$?

Например, рассмотрим строку $$$\texttt{abacaba}$$$. Вы можете сделать следующие ходы:

  • Заменить $$$\texttt{a}$$$ на $$$\texttt{0}$$$. Тогда строка будет иметь вид $$$\color{red}{\texttt{0}}\texttt{b}\color{red}{\texttt{0}}\texttt{c}\color{red}{\texttt{0}}\texttt{b}\color{red}{\texttt{0}}$$$.
  • Заменить $$$\texttt{b}$$$ на $$$\texttt{1}$$$. Тогда строка будет иметь вид $$${\texttt{0}}\color{red}{\texttt{1}}{\texttt{0}}\texttt{c}{\texttt{0}}\color{red}{\texttt{1}}{\texttt{0}}$$$.
  • Заменить $$$\texttt{c}$$$ на $$$\texttt{1}$$$. Теперь строка имеет вид $$${\texttt{0}}{\texttt{1}}{\texttt{0}}\color{red}{\texttt{1}}{\texttt{0}}{\texttt{1}}{\texttt{0}}$$$. Это чередующаяся бинарная строка.

$$$^{\dagger}$$$Чередующаяся бинарная строка — это такая строка из $$$\texttt{0}$$$ и $$$\texttt{1}$$$, что никакие два соседних символа не равны. Например, $$$\texttt{01010101}$$$, $$$\texttt{101}$$$, $$$\texttt{1}$$$ являются чередующимися бинарными строками, а $$$\texttt{0110}$$$, $$$\texttt{0a0a0}$$$, $$$\texttt{10100}$$$ — нет.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 2000$$$) — длина строки $$$s$$$.

Вторая строка каждого набора входных данных содержит строку, состоящую из $$$n$$$ строчных латинских букв — строка $$$s$$$.

Выходные данные

Для каждого набора входных данных выведите «YES» (без кавычек), если вы можете превратить строку в чередующуюся бинарную строку, и «NO» (без кавычек) в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
8
7
abacaba
2
aa
1
y
4
bkpt
6
ninfia
6
banana
10
codeforces
8
testcase
Выходные данные
YES
NO
YES
YES
NO
YES
NO
NO
Примечание

Первый набор входных данных объясняется в условии.

Во втором наборе входных данных единственными возможными бинарными строками, которые вы можете получить, являются $$$\texttt{00}$$$ и $$$\texttt{11}$$$. Но они обе не являются чередующимися.

В третьем наборе входных данных можно получить $$$\texttt{1}$$$, что является чередующейся бинарной строкой.