CF1494A.ABC String

You are given a string $a$, consisting of $n$ characters, $n$ is even. For each $i$ from $1$ to $n$ $a_i$ is one of 'A', 'B' or 'C'.

A bracket sequence is a string containing only characters "(" and ")". A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example, bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)"), and ")(", "(" and ")" are not.

You want to find a string $b$ that consists of $n$ characters such that:

• $b$ is a regular bracket sequence;
• if for some $i$ and $j$ ($1 \le i, j \le n$) $a_i=a_j$, then $b_i=b_j$.

In other words, you want to replace all occurrences of 'A' with the same type of bracket, then all occurrences of 'B' with the same type of bracket and all occurrences of 'C' with the same type of bracket.

Your task is to determine if such a string $b$ exists.

给你一个长度为 $n$ 的字符串 $a$，其中 $n$ 为偶数。对每个从 $1$ 到 $n$ 的 $i$，$a_i$ 是 'A'、'B' 或 'C' 中的一个字符。

括号序列是指仅由字符 '(' 和 ')' 组成的字符串。合法括号序列（regular bracket sequence）是指可以通过在原序列的字符之间插入字符 "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$。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.

Then the descriptions of $t$ testcases follow.

The only line of each testcase contains a string $a$. $a$ consists only of uppercase letters 'A', 'B' and 'C'. Let $n$ be the length of $a$. It is guaranteed that $n$ is even and $2 \le n \le 50$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

接下来是 $t$ 个测试用例的描述。

每个测试用例仅有一行，包含一个字符串 $a$。$a$ 仅由大写字母 'A'、'B' 和 'C' 组成。设 $n$ 为 $a$ 的长度。保证 $n$ 为偶数，且 $2 \le n \le 50$。

For each testcase print "YES" if there exists such a string $b$ that:

• $b$ is a regular bracket sequence;
• if for some $i$ and $j$ ($1 \le i, j \le n$) $a_i=a_j$, then $b_i=b_j$.

Otherwise, print "NO".

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES are all recognized as positive answer).

对于每个测试用例，如果存在满足以下条件的字符串 $b$，则输出 "YES"：

• $b$ 是一个合法的括号序列；
• 若对某些 $i$ 和 $j$（$1 \le i, j \le n$）有 $a_i = a_j$，则必有 $b_i = b_j$。

否则，输出 "NO"。

你可以以任意大小写形式输出每个字母（例如，字符串 yEs、yes、Yes 和 YES 均被视为肯定回答）。

In the first testcase one of the possible strings $b$ is "(())()".

In the second testcase one of the possible strings $b$ is "()()".

在第一个测试用例中，一个可能的字符串 $b$ 是 "(())()"。

在第二个测试用例中，一个可能的字符串 $b$ 是 "()()"。