Transform Binary String into Palindrome

You are given a binary string. Your task is to determine whether the string can be transformed into a palindrome by reversing any number of substrings of length 3. In one operation, you may choose any contiguous substring of exactly three characters and reverse its order. A string is a palindrome if it reads the same backwards as forwards.

For example, consider the following cases:

• For the string 101, no operation is needed since it is already a palindrome, so the answer is YES.
• For the string 1110, it is impossible to transform it into a palindrome with the allowed operations; hence, the answer is NO.
• For the string 101010, even though it is not initially a palindrome, a sequence of operations will transform it into one, so the answer is YES.

The underlying idea is to count the number of mismatched pairs of characters. If the string is already a palindrome (zero mismatches), the answer is YES. Otherwise, if twice the number of mismatches is divisible by 3, then it may be possible to balance the mismatches with a sequence of 3-character reversals, and the answer is YES; otherwise, the answer is NO.

inputFormat

The input begins with an integer T (T ≥ 1) representing the number of test cases. Each of the following T lines contains a binary string S (S consists only of characters '0' and '1').

outputFormat

For each test case, output a line containing YES if the binary string can be transformed into a palindrome using any number of reversals of substrings of length 3, or NO otherwise.## sample

5
101
1110
1100
000
101010

YES
NO
NO
YES
YES