Задана строка $$$a$$$, состоящая из $$$n$$$ символов, $$$n$$$ четно. Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ $$$a_i$$$ является одним из 'A', 'B' или 'C'.
Правильной скобочной последовательностью называется скобочная последовательность, которую можно преобразовать в корректное арифметическое выражение путем вставок между ее символами символов '1' и '+'. Например, скобочные последовательности «()()», «(())» — правильные (полученные выражения: «(1)+(1)», «((1+1)+1)»), а «)(» и «(» — нет.
Вы хотите найти такую строку $$$b$$$, которая состоит из $$$n$$$ символов, что:
Другими словами, вы хотите заменить все вхождения '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$$$, что:
Иначе выведите «NO».
Вы можете вывести каждую букву в любом регистре (например, YES, Yes, yes, yEs будут распознаны как положительный ответ).
4 AABBAC CACA BBBBAC ABCA
YES YES NO NO
В первом наборе входных данных одна из возможных строк $$$b$$$ равна «(())()».
Во втором наборе входных данных одна из возможных строк $$$b$$$ равна «()()».
