Anagram Palindrome Check

Given a string, determine whether its characters can be rearranged to form a palindrome. A string can form a palindrome if and only if the number of characters with an odd frequency is at most one, i.e., \(\#\{c \mid \text{freq}(c)\text{ is odd}\} \le 1\).

For example, the string aaabbbb can be rearranged into a palindrome (such as bbaaabb), so the answer is "YES". On the other hand, the string cdefg cannot be rearranged into a palindrome and the answer is "NO".

inputFormat

The input starts with an integer \(T\) indicating the number of test cases. Each of the next \(T\) lines contains a non-empty string \(s\) made up of lowercase letters.

outputFormat

For each test case, output "YES" if the string can be rearranged into a palindrome, otherwise output "NO". Each output should appear on a separate line.

3
aaabbbb
cdefg
aabbcc

YES
NO
YES