Rearrange to Palindrome

You are given a string consisting of lowercase English letters. Your task is to determine whether it is possible to rearrange the characters of the string such that the resulting string is a palindrome.

A palindrome is a string that reads the same forwards and backwards. Formally, a string S can be rearranged into a palindrome if and only if at most one character appears an odd number of times. For example, aabbcc can be rearranged to abc|cba and aaabbbb can be rearranged to abababa.

Your solution should process multiple test cases. Read the number of test cases T, and then for each test case, read the string and output YES if the string can be rearranged into a palindrome, or NO otherwise.

The solution should use standard input and output (stdin/stdout) for reading the input and writing the result.

inputFormat

The first line contains an integer T (1 ≤ T ≤ 10⁵), indicating the number of test cases. Each of the following T lines contains a non-empty string S consisting of lowercase letters. The length of each string will not exceed 10⁵.

outputFormat

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

## sample

3
aabbcc
aaabbbb
abcde

YES
YES
NO

</p>