Maximum Palindrome Length

You are given a string \( S \). Your task is to determine the maximum length of a palindrome that can be constructed using the characters in \( S \). A palindrome is a string that reads the same backward as forward.

To solve this problem, count the frequency of each character in \( S \). For characters that appear an even number of times, all of them can be used. For characters that appear an odd number of times, you can use \( (frequency - 1) \) characters and possibly one additional character can be placed in the middle of the palindrome.

Your solution should process multiple test cases from standard input and output the results to standard output.

inputFormat

The first line of input contains a single integer \( T \) \( (T \geq 0) \) representing the number of test cases. Each of the following \( T \) lines contains a single string \( S \) which consists of lowercase English letters.

outputFormat

For each test case, print the maximum length of a palindrome that can be built using the characters of the given string. Each result should be printed on a new line.

## sample

1
a

1

</p>