Palindromic Permutation Check

You are given a string s consisting of lowercase English letters. Your task is to determine whether any permutation of the string can form a palindrome.

A string is a palindrome if it reads the same forwards and backwards. It is well known that a permutation of a string can form a palindrome if and only if the number of characters with odd frequency is at most one. Mathematically, if we denote the frequency of each character c in the string by \( f(c) \), then a palindromic permutation exists if and only if:

[ \sum_{c \in s} [f(c) \bmod 2 \neq 0] \le 1 ]

Apply this logic to each test case.

inputFormat

The first line of input contains an integer T (1 ≤ T ≤ 10⁵) representing the number of test cases. Each of the following T lines contains a non-empty string s consisting of lowercase English letters.

Note: It is guaranteed that the sum of the lengths of all strings does not exceed 10⁶.

outputFormat

For each test case, output a single line containing YES if any permutation of the string forms a palindrome; otherwise, output NO.

## sample

3
aabb
abcba
abcd

YES
YES
NO

</p>