War Game

Gil-Dong has been playing a computer strategy game. To win it he has to work out the opponent's formation first, then line up soldiers that answer it. The game has three kinds of soldiers: archers, lancers, and horse riders. An archer beats a lancer, a lancer beats a horse rider, and a horse rider beats an archer. Given the opponent's formation, write a program that finds a winning formation for Gil-Dong with the fewest soldiers.

The rules are as follows.

1. Every soldier attacks straight ahead only and cannot attack to the side.
2. As in the figure, Gil-Dong's soldiers move from right to left and the opponent's soldiers move from left to right.
3. When one of Gil-Dong's soldiers meets an opponent soldier of the same kind, Gil-Dong's soldier loses, because his soldiers are not really well trained.
4. Only the loser of an engagement falls. The winner holds its place and immediately meets the next soldier of the other side.
5. Gil-Dong wins once every opponent soldier has fallen.

Your program reads from standard input. The first line holds the number of test cases $T$ ($1 \le T \le 15$). Each of the next $T$ lines holds one opponent formation as a string made only of A, B, and C, where A is an archer, B is a lancer, and C is a horse rider. No formation is longer than 80 characters. Note that the last soldier of the given formation is the one that meets the first soldier of Gil-Dong's formation.

Your program writes to standard output. For each test case print, on its own line, a winning formation of the minimum possible length, written starting from the soldier that fights first. The shortest winning formation is always unique.