给定一个字符串 $$$a$$$,由 $$$n$$$ 个字符组成,$$$n$$$ 是偶数。对于从$$$1$$$到$$$n$$$的每个$$$i$$$,$$$a_i$$$是“A”、“B”或“C”之一。
括号序列是仅包含字符“(”和“)”的字符串。正则括号序列是通过在序列的原始字符之间插入字符“1”和“+”,可以将括号序列转化为正确的算术表达式。例如,括号序列“()()”和“(())”是正规的(结果表达式是:“(1)+(1)”和“((1+1)+1)”),而“)(”、“(”和“)”则不是。
您想要查找由 $$$n$$$ 字符组成的字符串 $$$b$$$,如下所示:
- $$$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$$$。
输出
对于每个测试用例,如果存在这样的字符串 $$$b$$$ ,则打印“YES”:
- $$$b$$$ 是常规括号序列;
- 如果对于某些 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n$$$) $$$a_i=a_j$$$,则 $$$b_i=b_j$$$。
否则,打印“NO”。
您可以按您想要的任何大小写打印每个字母(例如,字符串 yEs、yes、Yes 和 YES 都被识别为肯定答案)。
示例
输入 #1
4 AABBAC CACA BBBBAC ABCA
输出 #1
YES YES NO NO
注意
在第一个测试用例中,可能的字符串 $$$b$$$ 是“(())()”。
在第二个测试用例中,可能的字符串 $$$b$$$ 之一是“()()”。