Palindrome Rearrangement

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

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 \in \Sigma} [f(c) % 2 \neq 0] \leq 1 ]

where \([P]\) is 1 if predicate \(P\) is true, and 0 otherwise. For each test case, output "YES" if it is possible, otherwise output "NO".

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 non-empty string \(s\) consisting of lowercase letters.

outputFormat

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

## sample

3
civic
ivicc
hello

YES
YES
NO

</p>