Longest Palindrome Length

Given a string s along with an integer n representing its length, determine the length of the longest palindrome that can be formed using the characters of the string. A palindrome is a string that reads the same forwards and backwards. You may rearrange the letters of the string arbitrarily. Note that you do not have to use all the characters.

The strategy is to count the frequency of each character. For each character with an even count, all occurrences can be used; for a character with an odd count, use the maximum even number of occurrences (i.e. count - 1) and if there is at least one character with an odd count, you can place one odd character in the center of the palindrome.

Hint (in \( \LaTeX \) ): For a given frequency \( f \) of a character, the contributable length is \[ \text{contribution} = \begin{cases} f, & \text{if } f \equiv 0 \; (\text{mod } 2) \\ f-1, & \text{if } f \equiv 1 \; (\text{mod } 2) \end{cases} \] and add 1 if any character has an odd frequency.

inputFormat

The first line of input contains a single integer T representing the number of test cases. Each test case consists of one line containing an integer n and a string s separated by a space. It is guaranteed that n equals the length of s.

outputFormat

For each test case, output a single line containing the length of the longest palindrome that can be formed with the characters of the given string.

## sample

3
5 aabbc
6 abcdef
4 aaaa

5
1
4

</p>