Longest Non-Adjacent Substring Rearrangement

You are given a string s consisting of lowercase letters. Your task is to determine the length of the longest substring that can be obtained by rearranging the characters of s so that no two adjacent characters are the same. If no such rearrangement exists, output -1.

A necessary and sufficient condition for a valid rearrangement is that the maximum frequency f_max of any character in s does not exceed \( \left\lfloor \frac{n+1}{2} \right\rfloor \), where \( n \) is the length of s.

For example:

• For s = "aaabbc", a valid rearrangement exists and the answer is 6.
• For s = "aaaaa", no valid rearrangement exists, so the answer is -1.
• For s = "aab", the answer is 3.

You need to process multiple test cases. For each test case, if a valid rearrangement is possible then the output is the length of the string (since you can use all characters); otherwise, output -1.

inputFormat

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

outputFormat

For each test case, output a single line containing an integer — the maximum length of the rearranged string if a valid rearrangement exists, or -1 if it is impossible.

## sample

6
aaabbc
aabbccddeeff
aaaaa
abcde
a
aab

6
12
-1
5
1
3

</p>