|Input file:||Standard input||Time limit:||1 sec|
|Output file:||Standard output||Memory limit:||512 Mb|
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.
Write a program that transforms a string into a correct hash by rearranging symbols in it or determines that it is impossible.
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.
For each string si output in a separate line:
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.
|No.||Standard input||Standard output|