Rearrangement of a and b Characters

Given a string s consisting only of characters 'a' and 'b', determine if it is possible to rearrange the characters such that no two adjacent characters are the same. A rearrangement is possible if and only if

$$|n_a - n_b| \leq 1,$$

where n_a is the number of occurrences of 'a' and n_b is the number of occurrences of 'b' in the string.

For example:

• For s = "aabb", the condition holds so the answer is Yes.
• For s = "aaab", the condition is violated since |3 - 1| = 2 > 1 so the answer is No.

inputFormat

The input is given from stdin and has the following format:

1. The first line contains an integer T representing the number of test cases.
2. The following T lines each contain a non-empty string s (with characters only 'a' and 'b').

outputFormat

For each test case, output a single line to stdout containing either Yes if it is possible to rearrange the string so that no two adjacent characters are the same, or No otherwise.

## sample

5
aabb
aaab
abab
aab
aaa

Yes
No
Yes
Yes
No

</p>