小园香径独徘徊

徘徊在一条幽深的小径上，拾起记忆的碎片，将它们放入两个长长的口袋中。 将它们收集完倒出来后，会拼成什么样的故事呢？

有两个字符串 $S,T$，一开始给定 $S$，$T$ 为空串。每次你可以执行以下三种操作，直到 $S$ 变为空串： 1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的开头； 1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的末尾； 1. 删去 $S$ 的最后一个字符，并将这个字符插入 $T$ 的开头。 a3 想知道，$S$ 变为空串后，可以构成的字典序最小的 $T$。

**本题有多组测试数据。** 第一行一个整数 $Q$，表示测试数据组数。 对于每组测试数据，一行一个字符串 $S$。

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

2
ababdca
dcbcadb

aaabbdc
abbcdcd

**【样例 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$ 仅由小写字母构成。