H. Reverse the String
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a string of lowercase letters, and you want to minimize its lexicographical order. What you can do is reverse an interval or do nothing.

For example, for the string abcdefg, if we reverse the interval abcdefg, it will become abfedcg.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

  • $$$a$$$ is a prefix of $$$b$$$, but $$$a\neq b$$$.
  • In the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.
Input

The first line contains an integer $$$T$$$ ($$$1\le T \le 20$$$), denoting the number of test cases.

For the following $$$T$$$ lines, each line contains a string $$$s$$$ of lowercase letters ($$$1\le |s|\le 10^5$$$, where $$$|s|$$$ is the length of $$$s$$$).

It is guaranteed that $$$\sum |s|\le 1.5\times 10^6$$$ over all test cases.

Output

For each test case, output the string with the minimal lexicographical order in a single line.

Example
Input
1
abbcabaac
Output
aaabacbbc