Migrated from Lutece 3060 双端字符串

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Natsuzora 有一个字符串 $S$，还有一个空串 $T$。Natsuzora 每次会从 $S$ 的左端或右端去取出一个字符，并插入到 $T$ 的尾部，直到 $S$ 中的字符被取完。

Natsuzora 想知道，他能够得到的字典序最小的 $T$ 是什么。

Input

本题包含多组数据。第一行一个整数 $n$ $(1\le n\le 5\times 10^4)$，表示数据组数。每组数据的格式如下：

一行一个字符串 $S$ $(1\le |S|\le 3\times 10^5)$，保证 $S$ 中只出现小写英文字母。

数据保证 $\sum |S|\le 3\times 10^5$。

Output

对于每组数据，输出一行一个字符串，表示能够得到的字典序最小的字符串 $T$。

Samples

1
bacbab

bababc

Note

$S$ 串初始为 $\text{bacbab}$。

首先从 $S$ 右端取出字符，于是 $S=\text{bacba}$，$T=\text{b}$；

然后从 $S$ 右端取出字符，于是 $S=\text{bacb}$，$T=\text{ba}$；

接着从 $S$ 左端取出字符，于是 $S=\text{acb}$，$T=\text{bab}$；

再从 $S$ 左端取出字符，于是 $S=\text{cb}$，$T=\text{baba}$；

最后从 $S$ 右端取出所有字符，$T=\text{bababc}$。

可以证明没有更优的方案。

Resources

2023 UESTC ICPC Training for String