Taco: Palindrome Rearrangement

You are given n strings. For each string, determine whether its characters can be rearranged to form a palindrome. A palindrome is a string that reads the same forwards and backwards. In other words, a string can be rearranged to form a palindrome if at most one character appears an odd number of times.

Formally, if the frequency of each character in a string is denoted by \(f(c)\), then the string can be rearranged into a palindrome if and only if \(\sum_{c}\mathbb{1}_{\{f(c)\ \text{is odd}\}} \le 1\).

Input: The first line contains an integer \(n\) representing the number of strings. This is followed by \(n\) lines each containing a string.

Output: For each string, output YES if it can be rearranged to form a palindrome, and NO otherwise.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer \(n\) denoting the number of test strings. Each of the next \(n\) lines contains one string \(s\).

outputFormat

For each test string, print a single line containing either YES if the string can be rearranged to form a palindrome, or NO otherwise. The output should be written to standard output (stdout).

## sample

3
aabb
abc
racecar

YES
NO
YES

</p>