Longest Palindrome Construction

Given a string s, determine the length of the longest palindrome that can be constructed using the characters of s. In other words, you can rearrange the characters of s to build a palindrome. The idea is to use as many characters as possible by pairing them, and if there is any character left unpaired, one of them can be placed in the center.

The length is computed as follows: for each character, add its count if the count is even, or add count - 1 if the count is odd. If there exists any odd count, add 1 to the total. Mathematically, you may express it as:

\[ \text{result} = \sum_{c \in s} \left( \lfloor \frac{\text{count}(c)}{2} \rfloor \times 2 \right) + \begin{cases} 1 & \text{if any } \text{count}(c) \text{ is odd} \\ 0 & \text{otherwise} \end{cases} \]

The input will contain multiple queries. For each query, output the computed length.

inputFormat

The first line contains an integer T (1 ≤ T ≤ 10⁵), the number of queries. Each of the next T lines contains a non-empty string s consisting of lowercase and/or uppercase letters.

For example:

3
abccccdd
a
bb

outputFormat

Output T lines. Each line should contain a single integer representing the length of the longest palindrome that can be constructed from the corresponding input string.

For the sample input above, the output should be:

7
1
2

## sample

3
abccccdd
a
bb

7
1
2

</p>