Palindrome Rearrangement

You are given a string and you need to determine whether its characters can be rearranged to form a palindrome. A palindrome is a string that reads the same forwards and backwards.

The necessary and sufficient condition for a string to be rearranged to form a palindrome is that at most one character appears an odd number of times. More formally, let \( f(c) \) be the frequency of character \( c \) in the string. The string can be rearranged to form a palindrome if and only if:

\( \sum_{c} \mathbf{1}_{\{ f(c) \mod 2 \neq 0 \}} \leq 1 \)

Given multiple test cases, solve the problem for each string.

inputFormat

The first line of input contains a single integer ( t ) (( 1 \leq t \leq 10^5 )), denoting the number of test cases. Each of the next ( t ) lines contains a non-empty string ( s ) consisting of lowercase or uppercase English letters.

outputFormat

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

4
aabb
abc
racecar
aabbccdd

YES
NO
YES
YES