给定一个由小写字母组成的字符串，你希望将其字典序最小化。你可以进行的操作是：反转字符串中的一个区间，或者什么都不做。

例如，对于字符串 abcdefg，如果我们反转区间 abcdefg，它将变为 abfedcg。

字符串 $a$ 的字典序小于字符串 $b$ 当且仅当满足以下条件之一：

• $a$ 是 $b$ 的前缀，但 $a \neq b$。
• 在 $a$ 和 $b$ 第一个不同的位置上，$a$ 对应的字母在字母表中出现的位置比 $b$ 对应的字母更靠前。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 20$)，表示测试用例的数量。 接下来的 $T$ 行，每行包含一个由小写字母组成的字符串 $s$ ($1 \le |s| \le 10^5$，其中 $|s|$ 为 $s$ 的长度)。 保证所有测试用例的 $|s|$ 之和不超过 $1.5 \times 10^6$。

输出格式

对于每个测试用例，输出一行，包含字典序最小的字符串。

样例

输入格式 1

1
abbcabaac

输出格式 1

aaabacbbc