Palindrome Rearrangement

You are given a string S and you need to determine whether some permutation of the characters of S can form a palindrome.

A palindrome is a string that reads the same backwards as forwards. For a string to be rearranged into a palindrome, the frequency of characters must satisfy a particular condition: at most one character can have an odd frequency. In other words, if we let \( c_i \) be the count of the \( i\)-th character, then the string can form a palindrome if and only if

\( \sum_{i} [c_i \bmod 2] \leq 1 \)

Your task is to determine for each test case whether the string can be rearranged to form a palindrome.

inputFormat

The first line of input contains an integer T (\(1 \le T \le 10^5\)) representing the number of test cases.

This is followed by T lines, each containing a single string S consisting of lowercase English letters. The length of each string will be at least 1 and at most \(10^5\). The sum of the lengths of all strings does not exceed \(10^6\).

outputFormat

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

## sample

5
civic
ivicc
hello
a
aa

YES
YES
NO
YES
YES

</p>