Palindrome Rearrangement

Given a string, determine if the characters can be rearranged to form a palindrome. A palindrome is a string that reads the same forwards and backwards.

For each test case, output YES if the string can be rearranged into a palindrome, otherwise output NO.

The solution should handle multiple test cases provided via standard input (stdin) and produce the correct answers on standard output (stdout).

The necessary condition for a string to be rearranged into a palindrome is that at most one character appears an odd number of times. Formally, if the frequency of characters in the string is given by \(f(c)\), then the string can be rearranged into a palindrome if and only if \(\sum_{c} [f(c)\%2 \neq 0] \leq 1\).

inputFormat

The first line of input contains an integer \(T\) \( (1 \leq T \leq 10^5) \) representing the number of test cases. Each of the following \(T\) lines contains a single non-empty string \(S\) consisting of lowercase English letters (\(a\)–\(z\)).

outputFormat

For each test case, print a single line containing YES if the string can be rearranged into a palindrome, otherwise output NO.

## sample

3
aabb
abcde
carerac

YES
NO
YES

</p>