Permutation Palindrome

You are given a string s. Determine if any permutation of s can form a palindrome. A palindrome is a string that reads the same backward as forward. In other words, check whether the characters of s can be rearranged such that they form a palindrome.

Note: A string can be rearranged into a palindrome if and only if the number of characters with an odd frequency is at most one, i.e., $$\text{odd_count} \le 1$$.

inputFormat

The first line contains a single integer T (1 ≤ T ≤ 10⁵), the number of test cases.

Each of the next T lines contains a non-empty string s consisting of lowercase English letters. The length of each string is at most 10³.

outputFormat

For each test case, output a single line containing YES if some permutation of s can form a palindrome, otherwise output NO.

3
aabb
abc
carerac

YES
NO
YES