Longest Palindromic Substring Rearrangement

You are given a string s consisting of lowercase English letters. Your task is to determine the length of the longest substring of s that can be rearranged to form a palindrome.

A palindrome is a string that reads the same backwards as forwards. In order to form a palindrome, each character in the string must appear an even number of times, except possibly one character which may appear an odd number of times (this character would occupy the center position in the palindrome). Formally, if the frequency of a character is f, you can contribute f to the length if f is even, or f-1 if f is odd. Additionally, if there is any odd frequency, you can add 1 to the length for the center of the palindrome. In mathematical notation, the answer can be derived by:

$$L = \sum_{c \in S} \left( f(c) - (f(c) \bmod 2) \right) + \begin{cases} 1, & \text{if any } f(c) \bmod 2 = 1 \\ 0, & \text{otherwise} \end{cases} $$

Process multiple test cases, each consisting of a single string.

inputFormat

The first line contains a single integer T (1 ≤ T ≤ 10⁵), the number of test cases. Each of the next T lines contains a non-empty string s consisting of lowercase English letters.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single integer, the length of the longest substring of s that can be rearranged to form a palindrome. Each answer should be printed on a new line on standard output (stdout).

## sample

2
abc
aaabbbcc

1
7

</p>