Description

有两个字符串 $S,T$，一开始给定 $S$，$T$ 为空串。每次你可以执行以下三种操作，直到 $S$ 变为空串：

1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的开头；
2. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的末尾；
3. 删去 $S$ 的最后一个字符，并将这个字符插入 $T$ 的开头。

a3 想知道，$S$ 变为空串后，可以构成的字典序最小的 $T$。

Input Format

本题有多组测试数据。

第一行一个整数 $Q$，表示测试数据组数。

对于每组测试数据，一行一个字符串 $S$。

Output Format

对于每组测试数据，一行一个字符串，表示可以构成的字典序最小的 $T$。

2
ababdca
dcbcadb

aaabbdc
abbcdcd

Hint

【样例 1 解释】

• 对于 $\texttt{ababdca}$，依次进行第 $1,2,1,2,2,2,1$ 种操作，即可得到 $\texttt{aaabbdc}$。
• 对于 $\texttt{dcbcadb}$，依次进行第 $1,1,1,2,3,1,2$ 种操作，即可得到 $\texttt{abbcdcd}$。

【数据规模与约定】

本题采用捆绑测试。

• Subtask 1（5 points）：$S$ 由至多两种字符构成。
• Subtask 2（10 points）：$\sum |S|\le 12$。
• Subtask 3（15 points）：$\sum |S|\le 100$。
• Subtask 4（25 points）：$\sum |S|\le 3\times 10^3$。
• Subtask 5（20 points）：$\sum |S|\le 2\times 10^5$。
• Subtask 6（25 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le Q\le 3\times 10^5$，$1\le |S|\le 10^6$，$1\le \sum |S|\le 2\times 10^6$，$S$ 仅由小写字母构成。