Longest Even-Length Palindrome Construction

Given a string S consisting of lowercase English letters, determine the length of the longest even-length palindrome that can be constructed by rearranging its characters.

The palindrome must use characters from S in any order. In other words, for each character, you can use it as many times as allowed by its frequency in S, but each selected character must appear an even number of times in the palindrome.

Constraints:

• T (the number of test cases) is an integer between 1 and 20, inclusive.
• For each test case, the input string S has a length between 1 and 200, inclusive and must consist solely of lowercase letters.

If any of the inputs do not satisfy these constraints, output Invalid Input (without quotes) for that test case or overall if T is invalid.

For example, consider the string aabbcc. The longest even-length palindrome that can be formed is of length 6 (one possible arrangement is abc|cba), while for abcde no even-length palindrome can be formed (thus output is 0).

Note: All formulas (if any) are rendered in \(\LaTeX\) format. For instance, a frequency count for a character \(c\) can be expressed as:

\[ \text{freq}(c)=\#\{i:\;S[i]=c\} \]

inputFormat

The input is read from stdin and is structured as follows:

T
S1
S2
...
ST

Where:

• T: An integer representing the number of test cases.
• Each of the following T lines contains a single string S.
• If T is not within [1,20] or any string S is not of length [1,200] or contains characters other than lowercase English letters, the output should be Invalid Input.

outputFormat

The output is printed to stdout. For each test case, print a single line containing the length of the longest even-length palindrome that can be constructed using the characters of string S. If the input is invalid for any test case or overall, print Invalid Input.

## sample

1
aabbcc

6

</p>