Longest Palindrome Length

This problem requires you to determine the maximum length of a palindrome that can be constructed by rearranging (and optionally replacing) the characters of a given string. In other words, for a string s, you need to calculate the maximum palindrome length using the characters available.

The solution is based on counting each character's frequency and using the following formula:

$$\text{Answer} = \sum_{c \in s} \Big( count(c) - (count(c) \mod 2) \Big) + \min(1, \text{\# of odd counts}) $$

For example, given the string "abccccdd", the output is 7 because you can form the palindrome "dccaccd" (or any other valid permutation with the same counts).

inputFormat

The first line contains an integer t representing the number of test cases. Each of the following t lines contains a single string s consisting of lowercase letters.

You should read from stdin.

outputFormat

For each test case, output a single integer on its own line representing the maximum length of a palindrome that can be built using the characters in the string.

Write your answer to stdout.

## sample

3
abccccdd
aabb
abcde

7
4
1

</p>