Rearranging Characters to Form a Palindrome

You are given a list of strings. For each string, determine whether its characters can be rearranged to form a palindrome.

A string is called a palindrome if it reads the same backward as forward. In order for a string to be rearranged into a palindrome, at most one character can have an odd frequency. Mathematically, if the frequency of each character in the string is given by \(f(c)\), then the condition for the string to be rearranged into a palindrome is:

\(\sum_{c \in S} \mathbf{1}_{\{f(c)\ \%\ 2 \neq 0\}} \le 1\)

For each test case, output YES if the string meets the condition; otherwise, output NO.

inputFormat

The input is read from standard input and has the following format:

1. The first line contains an integer T (1 ≤ T ≤ 10⁴), representing the number of test cases.
2. The next T lines each contain a non-empty string consisting of lowercase or uppercase letters.

outputFormat

For each test case, output a line containing YES if it is possible to rearrange the string into a palindrome, otherwise output NO.

3
carrace
hello
aabbcc

YES
NO
YES