Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

You are given a string \(S\) consisting of lowercase English letters. Your task is to rearrange the characters of \(S\) so that no two adjacent characters are the same.

If multiple such rearrangements are possible, you must output the lexicographically smallest one. If it is impossible to rearrange the string under the given condition, output -1.

Input

• The first line contains an integer \(T\) (\(1 \leq T \leq 100\)) — the number of test cases.

• Each of the next \(T\) lines contains a single string \(S\) (\(1 \leq |S| \leq 5 * 10^3\)) consisting of lowercase English letters.

• It is guaranteed that the sum of lengths of all strings across all test cases does not exceed \(5 * 10^3\).

Output

• For each test case, print a single line containing the answer:

  • a rearranged string such that no two adjacent characters are the same and it is lexicographically smallest among all such rearrangements, or

  • if no such rearrangement is possible, print -1.

Sample

10
cc
bcbbbcac
acbcb
b
bcbbbccacb
aabca
cbcccacbc
cccabcaaa
bca
bbabc

-1
abcbcbcb
abcbc
b
abcbcbcbcb
abaca
-1
abcacacac
abc
babcb

Consider Third test case:
There are 12 possible valid rearrangement.
"abcbc", "acbcb", "bacbc", "bcabc", "bcacb", "bcbac", "bcbca", "cabcb", "cbabc", "cbacb", "cbcab", "cbcba".
Lexicographically smallest: "abcbc".