Palindromic Permutation

Given a string s, determine if any permutation of its characters can form a palindrome. A palindrome is a sequence that reads the same backward as forward. Formally, let \(f(c)\) be the frequency of character \(c\) in the string \(s\). A rearrangement of \(s\) can form a palindrome if and only if \(\sum_{c}\big[f(c) \bmod 2 \neq 0\big] \le 1\), where the sum counts the number of characters with an odd frequency.

inputFormat

The input begins with a single integer \(T\) indicating the number of test cases. Each of the following \(T\) lines contains a string \(s\) consisting of alphabetical characters.

outputFormat

For each test case, output a single line containing YES if any permutation of \(s\) can form a palindrome, otherwise output NO.

3
civic
ivicc
hello

YES
YES
NO