Problem I. Imictcoin

Input file:Standard input   Time limit:1 sec
Output file:Standard output   Memory limit:512 Mb

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:

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 si. Each string consists of lowercase Latin letters.

Output format

For each string si output in a separate line:

Constraints

1 ≤ T ≤ 104.

The length of si is no more than 5⋅ 105. The total length of all strings in a single test is no more than 5⋅ 105.

Sample tests

No. Standard input Standard output
1
2
aabb
aaaabb
abab
-1
2
1
a
a

0.217s 0.039s 13