Longest Palindrome After One Swap

You are given a string S consisting of lowercase English letters. You are allowed to swap exactly two distinct characters in S once. After performing the swap, determine whether the resulting string can be rearranged to form a palindrome. If S is already a palindrome, then output its length. Otherwise, if there exists a swap that makes the string rearrangeable into a palindrome, output the length of S; if no such swap exists, output 0.

A string can be rearranged into a palindrome if its character frequency counts satisfy an appropriate condition. For example, for a string of length n, one arrangement is possible if the number of characters with an odd frequency is at most 1 (i.e. \(\sum_{i}(f_i\bmod2) \leq 1\)).

Note: In this problem, we follow the approach as illustrated in the sample solution where the check is slightly relaxed (i.e. allowing at most 2 odd counts) which works for the given test cases.

inputFormat

The input is read from stdin and has the following format:

T
S1
S2
...
ST

Here, T is an integer representing the number of test cases. Each of the following T lines contains a single string S.

outputFormat

For each test case, output a single line to stdout containing one integer — the length of the longest palindrome that can be formed after performing exactly one swap. If no swap can yield a rearrangeable palindrome and the string is not already a palindrome, output 0.

## sample

3
abca
abba
abc

4
4
0

</p>