Rearrange String to Avoid Adjacent Duplicates

You are given a string S. Your task is to rearrange the characters of S such that no two adjacent characters are the same. Among all valid rearrangements, you must output the lexicographically smallest one. If no valid rearrangement exists, output -1.

A necessary and sufficient condition for the existence of a valid rearrangement is that for the given string of length n, the frequency of every character f(c) satisfies $$ f(c) \le \frac{n+1}{2} $$ If this condition fails for any character, the answer is -1.

Example:

• For S = "aab", one valid answer is "aba".
• For S = "aaab", no valid rearrangement exists so the answer is -1.
• For S = "abc", the answer is "abc" because it is already valid and lexicographically smallest.

inputFormat

The input is given via standard input (stdin) and has the following format:

T
S1
S2
...
ST

Here, T is the number of test cases, and each Si is a non-empty string consisting of lowercase English letters.

outputFormat

For each test case, output the rearranged string on a new line. If it is impossible to rearrange to meet the condition, output -1.

## sample

3
aab
aaab
abc

aba
-1
abc

</p>