Nežmah 先生发现了一个长度为 $n$ 的大字符串；事实上，它大到被称为一根“粗缆”（hawser）更为合适。然而，他想从中恰好删去一个字母。在通过这种方式可以得到的 $n$ 个字符串中，他对字典序中位数感兴趣。

形式化地，设 $t_i$ 表示从 $s$ 中删去第 $i$ 个字母后得到的字符串。设 $p$ 为 $1$ 到 $n$ 的一个排列，满足对于所有 $1 \le i < n$，$t_{p_i}$ 在字典序上小于或等于 $t_{p_{i+1}}$。他想知道 $t_{p_{\lfloor \frac{n+1}{2} \rfloor}}$。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 2 \cdot 10^4$)，表示测试用例的数量。

每个测试用例的唯一一行包含一个字符串 $s$ ($2 \le |s| \le 10^6$)，仅由小写英文字母组成。

所有测试用例中 $|s|$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，在单行中输出所需的字符串。

样例

输入样例 1

4
zagreb
klokani
oblutci
abc

输出样例 1

zagrb
klokan
oblutc
ac