Rearrange to Palindrome

You are given a string and your task is to determine whether its characters can be rearranged to form a palindrome. A string is a palindrome if it reads the same backwards as forwards.

Formally, let the frequency of each character be denoted by (n_c). A rearrangement to form a palindrome is possible if and only if (\sum_{c \in S} \mathbf{1}(n_c \bmod 2 \neq 0) \leq 1).

For each test case, output YES if the string can be rearranged into a palindrome, otherwise output NO.

inputFormat

The input begins with a single integer (T) ((1 \leq T \leq 10^5)) representing the number of test cases. The following (T) lines each contain a non-empty string consisting of lowercase English letters.

outputFormat

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

2
carrace
daily

YES
NO