Check Palindrome Permutation

You are given T strings. For each string, determine whether it is possible to rearrange its characters to form a palindrome. A string can be rearranged into a palindrome if at most one character occurs an odd number of times. In other words, for a string s, count the frequency of each character. If the number of characters with an odd frequency is less than or equal to one, then s can be permuted into a palindrome.

Note: The input strings do not contain spaces and are provided one per line.

The formal condition can be written in LaTeX as follows:

$$\text{Let } f(c) \text{ be the frequency of character } c \text{ in } s. \text{ Then, } s \text{ can form a palindrome if } \sum_{c} \mathbf{1}_{\{f(c) \bmod 2 \neq 0\}} \leq 1. $$

inputFormat

The first line of input contains a single integer T representing the number of test cases. Each of the following T lines contains a non-empty string s composed of only lowercase letters.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing "YES" if the string can be rearranged to form a palindrome, and "NO" otherwise.

Output is written to standard output (stdout).

## sample

1
civic

YES

</p>