A. Строка ABC
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана строка $$$a$$$, состоящая из $$$n$$$ символов, $$$n$$$ четно. Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ $$$a_i$$$ является одним из 'A', 'B' или 'C'.

Правильной скобочной последовательностью называется скобочная последовательность, которую можно преобразовать в корректное арифметическое выражение путем вставок между ее символами символов '1' и '+'. Например, скобочные последовательности «()()», «(())» — правильные (полученные выражения: «(1)+(1)», «((1+1)+1)»), а «)(» и «(» — нет.

Вы хотите найти такую строку $$$b$$$, которая состоит из $$$n$$$ символов, что:

  • $$$b$$$ является правильной скобочной последовательностью;
  • если для некоторых $$$i$$$ и $$$j$$$ ($$$1 \le i, j \le n$$$) $$$a_i=a_j$$$, тогда $$$b_i=b_j$$$.

Другими словами, вы хотите заменить все вхождения 'A' скобками одного типа, затем все вхождения 'B' скобками одного типа и все вхождения 'C' скобками одного типа.

Ваша задача — определить, существует ли такая строка $$$b$$$.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Затем следуют описания $$$t$$$ наборов входных данных.

В единственной строке каждого набора входных данных содержится одна строка $$$a$$$. $$$a$$$ состоит только из заглавных букв 'A', 'B' и 'C'. Пусть $$$n$$$ будет длиной строки $$$a$$$. Гарантируется, что $$$n$$$ четно и что $$$2 \le n \le 50$$$.

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

Для каждого набора входных данных выведите «YES», если существует такая строка $$$b$$$, что:

  • $$$b$$$ является правильной скобочной последовательностью;
  • если для некоторых $$$i$$$ и $$$j$$$ ($$$1 \le i, j \le n$$$) $$$a_i=a_j$$$, тогда $$$b_i=b_j$$$.

Иначе выведите «NO».

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

Пример
Входные данные
4
AABBAC
CACA
BBBBAC
ABCA
Выходные данные
YES
YES
NO
NO
Примечание

В первом наборе входных данных одна из возможных строк $$$b$$$ равна «(())()».

Во втором наборе входных данных одна из возможных строк $$$b$$$ равна «()()».