In the game of The Last Word, Motu begins a round by showing Chotu a string S. Chotu has a whiteboard which is initially blank. Motu will then present Chotu with the letters of S, one by one, in the order in which they appear in S. When Motu presents the first letter, Chotu writes it on the whiteboard, this counts as the first word in the game (even though it is only one letter long). After that, each time Motu presents a letter, Chotu must write it at the beginning or the end of the word on the whiteboard before Motu moves on to the next letter (or to the end of the game, if there are no more letters).

For example, for S = CAB, after writing the word C on the whiteboard, Chotu could make one of the following four sets of choices:

put A before C to form AC, then put B before AC to form BAC

put A before C to form AC, then put B after AC to form ACB

put A after C to form CA, then put B before CA to form BCA

put A after C to form CA, then put B after CA to form CAB

Winning word is the lexicographically largest word that can be produced using above mentioned rules.

Help Chotu to find winning word.

Input

First line contains an integer T denoting number of test cases. Next T lines contain a string S.

Output

For each input print its corresponding winning word.

Constraints

1 ≤ T ≤ 10
1 ≤ |S| ≤ 1000
S contains UPPERCASE LETTERS