Tangsuyuk Game

Hwangyu and Taewook play a simple two-player game called the tangsuyuk game. The rules are these.

1. The two players decide who speaks first.
2. The player who starts says the first syllable of the word.
3. From then on the players take turns, and on your turn you say the syllable that follows the one the other player just said.
4. If the other player said the last syllable of the word, you say the first syllable of the word on your turn.
5. If you say a wrong syllable on your turn, you lose.

Take the word "tangsuyuk", split into the syllables tang, su, yuk. The game then runs tang, su, yuk, tang, su, yuk, tang, su, yuk, and so on. The player who starts takes the first, third, and fifth positions, so what that player actually says is tang, yuk, su, tang, yuk, su, and so on. Memorizing "tangyuksu" before the game and repeating it in that order is enough to never make a mistake, whatever the other player says.

Memorizing "tangyuk" or "tangyuksutang" does not work: repeating the memorized string from its start produces a wrong syllable on one of your turns and you lose. Memorizing "tangyuksutangyuksu" never produces a wrong syllable, but "tangyuksu" already carries the game, so the answer is the shortest string that has to be memorized. The player who starts second is in the same position: memorizing "sutangyuk" and repeating it in that order never produces a mistake.

This time the two players use the Latin alphabet instead of Korean syllables. If the word is "ABC" and Hwangyu starts, Hwangyu memorizes "ACB" and Taewook memorizes "BAC", and neither of them loses. Given the alphabet string used in the game, write a program that prints the shortest string each of the two players has to memorize in advance.

Input is read from standard input. The first line holds a natural number $T$, the number of test cases. The first line of each test case holds the string used in the game. The length of the string is at least 1 and at most 26. The string consists of uppercase letters only and never contains the same letter twice.

Output is written to standard output. For each test case print two lines, in the order the test cases are given. The first line holds the shortest string the player who starts first has to memorize, and the second line holds the shortest string the player who starts second has to memorize. Print both in uppercase letters.