Palindromic Rearrangement

Given a string, determine if it is possible to rearrange its characters so that the string becomes a palindrome. A palindrome is a string that reads the same forward and backward. For example, the string 'aabb' can be rearranged into 'abba' or 'baab', which are palindromes, while the string 'abc' cannot be rearranged into any palindrome.

The mathematical condition is that at most one character can have an odd frequency. Formally, let ( count(c) ) denote the frequency of character ( c ) in the string. Then, the string can be rearranged to form a palindrome if and only if ( \sum_{c} \mathbf{1}{ count(c) \mod 2 \neq 0 } \leq 1 ).

inputFormat

The first line contains an integer (T) ((1 \leq T \leq 10^5)), the number of test cases. Each of the following (T) lines contains a single string (s) consisting of lowercase letters. You should determine for each string if it can be rearranged to form a palindrome.

outputFormat

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

3
aabb
aaa
abc

YES
YES
NO