Palindrome Rearrangement

You are given an integer T representing the number of test cases. For each test case, you are provided with a string S. Your task is to determine whether the characters of the string can be rearranged to form a palindrome.

A string is a palindrome if it reads the same forwards and backwards. A rearrangement is possible if and only if at most one character appears an odd number of times. In mathematical notation, let \( f(c) \) be the frequency of character \( c \) in the string. The string can be rearranged into a palindrome if:

\[ \sum_{c \in S} \left[ f(c) \bmod 2 \neq 0 \right] \le 1 \]

Output "YES" if the string can be rearranged into a palindrome and "NO" otherwise.

inputFormat

The first line of input contains a single integer T (\(1 \le T \le 10^5\)) denoting the number of test cases. Each of the next T lines contains a string S consisting of lowercase English letters. The length of \(S\) will be at least 0 and at most 1000.

outputFormat

For each test case, output a single line containing "YES" if it is possible to rearrange the characters of the string to form a palindrome, or "NO" otherwise.

## sample

3
civic
ivicc
hello

YES
YES
NO

</p>