Palindromic Rearrangement Check

Given a string s consisting of lowercase English letters, determine if it is possible to rearrange the characters of the string to form a palindrome.

A palindrome is a sequence that reads the same backward as forward. A necessary and sufficient condition for the existence of such a rearrangement is that at most one character in the string has an odd frequency. In other words, if you count how many times each character appears, no more than one of those counts should be odd.

For example:

• civic can be rearranged to form a palindrome (itself is a palindrome), so the answer is YES.
• ivicc can also be rearranged into civic, so the answer is YES.
• hello cannot be rearranged to form a palindrome, so the answer is NO.

The mathematical condition for a string s to be rearranged into a palindrome can be written in LaTeX as: $$\text{Let } f(c) \text{ be the frequency of character } c, \text{ then } \sum_{c \in s} [f(c) \bmod 2] \leq 1.$$

inputFormat

The input is read from standard input and is structured as follows:

• The first line contains an integer T, the number of test cases.
• Each of the following T lines contains a single string s consisting of lowercase English letters.

outputFormat

For each test case, output on a separate line YES if the string can be rearranged to form a palindrome, otherwise output NO.

## sample

3
civic
ivicc
hello

YES
YES
NO

</p>