Removable String

Given a string S, you are allowed to perform the following operation as many times as you wish:

• If there is a character that can be paired with the last unpaired character in a left-to-right iteration such that they are different, remove the last unpaired character along with the current character.

Formally, you can process the string from left to right, maintaining a stack. For each character c in the string, if the stack is non-empty and the top of the stack is a character different from c, then remove the top character (thus pairing it with c). Otherwise, push c onto the stack. At the end, if the stack is empty, then it is possible to remove all characters using the allowed operations. Otherwise, it is not.

You are to determine for each test case whether it is possible to completely remove the string.

The process can be mathematically illustrated as follows. Let the operation be applied on a string S as:

$$ \text{if } S = A\,a\,B\,b\,C \text{ with } a \neq b, \text{ then } S \to A\,B\,C. $$

The answer is YES if after a series of operations the string becomes empty, otherwise NO.

inputFormat

The input begins with a single integer t representing the number of test cases. Each of the following t lines contains a non-negative string S consisting of lowercase English letters. Note that S can be empty.

Example:

4
abccba
abcba
aabb
abab

outputFormat

For each test case, output a single line: YES if it is possible to completely remove all the characters from the string using the allowed operations, or NO otherwise.

## sample

4
abccba
abcba
aabb
abab

YES
NO
YES
YES

</p>