Problem I. Imictcoin ≡

Statement

Following the founding of a new institute in a well-known university its best programmers decided to create their own crypto currency "Imictcoin". But the chief cybersecurity expert Sergey came up with a special set of rules to compute hash for each block in a blockchain.

Hash must be a sequence of Latin letters that satisfies a single condition — not a single symbol can appear twice in a row.

For example:

• s = "abababc" is correct hash;
• s = "aabcabab" is incorrect hash;
• s = "a" is also correct hash.

Write a program that transforms a string into a correct hash by rearranging symbols in it or determines that it is impossible.

Input format

The first line of the input contains a single integer T — number of input strings. The following T lines each contain a single string s_i. Each string consists of lowercase Latin letters.

Output format

For each string s_i output in a separate line:

• -1, if the correct hash cannot be obtained;
• a string, representing a correct hash, which is a permutation of symbols of string s_i.

Constraints

1 ≤ T ≤ 10⁴.

The length of s_i is no more than 5 ⋅ 10⁵. The total length of all strings in a single test is no more than 5 ⋅ 10⁵.

Sample tests

2
aabb
aaaabb

abab
-1

1
a

a