Read problems statements in Mandarin Chinese and Russian as well.

Today is Devu's birthday. He has obtained few colored balloons from his friends. You are given this information by a string s consisting of lower case English Latin letters. Each letter (from 'a' to 'z') denotes a color. e.g. if s = "aab", then it means that he has received two balloons of color 'a' whereas one balloon of color 'b'.

Now, Devu wants to decorate the cake by arranging all the balloons linearly from left to right on the cake such that no same colored balloons are nearby/ adjacent to each other.

Now Devu wonders whether it is possible to do so or not? Please help him in this. If it is not possible to do so, print -1. Otherwise, print any one of arrangements of the balloons on the cake. If there are more than one possible ways of doing so, you can print any one of them.

------ Input ------

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
First line of each test case will contain string s

------ Output ------

Print a single line corresponding to the answer of the problem.

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ size of string s ≤ 10^{5}$
$Sum of size of string s over all test cases will be less than or equal to ≤ 10^{6}$

----- Sample Input 1 ------
3
aab
ab
aa
----- Sample Output 1 ------
aba
ab
-1
----- explanation 1 ------
Example case 1. He can arrange the balloons in the order given by the following string "aba".
Example case 2. He can arrange the balloons in the order given by the following string "ab"
Example case 3. There is no valid way of decorating cakes with balloon in the desired way. So we print -1.

见题面

见题面