Maximum Distinct Adjacent Characters

Given a string s, rearrange its characters such that adjacent characters are distinct. Your task is to determine the maximum number of characters in the rearranged string. If it is not possible to rearrange the string to meet the condition, output -1.

It can be proven that if a valid rearrangement exists, the maximum possible output is \(n\), where \(n\) is the length of the string. Otherwise, if there exists a character whose frequency exceeds \(\left\lceil \frac{n}{2} \right\rceil\), the answer is \(-1\).

inputFormat

The first line of input contains an integer \(T\), representing the number of test cases. Each of the following \(T\) lines contains a non-empty string \(s\) consisting of lowercase letters.

outputFormat

For each test case, print a single integer on a new line, which is the maximum number of distinct adjacent characters possible after rearrangement, or \(-1\) if no valid rearrangement exists.

5
aabb
abac
abcd
aaa
aab

4
4
4
-1
3