Taco Palindrome Puzzle

You are given a number of test cases t. For each test case, you are given a string. Your task is to determine whether the characters of the string can be rearranged to form a palindrome.

A string can be rearranged into a palindrome if at most one character appears an odd number of times. For example, the string aabb can be rearranged into abba (a palindrome) while abc cannot form any palindrome.

Print YES if the string can be rearranged to form a palindrome, otherwise print NO.

Note: Use standard input (stdin) and output (stdout).

inputFormat

The first line contains an integer t (1 ≤ t ≤ 10⁵) — the number of test cases.

Each of the following t lines contains a non-empty string composed of lowercase English letters.

outputFormat

For each test case, output a single line containing YES if the string can be rearranged to form a palindrome, or NO otherwise.

## sample

3
aabb
abc
aaabb

YES
NO
YES

</p>