P16968 [SCCPC 2026] 博德之跃 3

给定一个由小写英文字母组成的字符串 $S$，以及一个初始为空的字符串 $T$。 你需要对 $S$ 执行若干次操作，直到它变为空字符串。每次你可以执行以下三种操作中的一种： - 删除 $S$ 的第一个字符，并将其添加到 $T$ 的末尾。 - 删除 $S$ 的最后一个字符，并将其添加到 $T$ 的末尾。 - 选择非空串 $A,B$ 满足 $S = ABA^R$，令 $S=B$ 并将字符串 $A$ 添加到 $T$ 的末尾。 其中 $A^R$ 表示字符串 $A$ 的反串。 求在所有操作方案中，能得到的字典序最小的 $T$。

本题有多组测试数据。 输入第一行一个正整数 $t$（$1 \le t \le 10^5$），表示测试数据组数。 每组测试数据： 输入一行一个由小写字母组成的字符串 $S$（$1 \le |S| \le 5 \times 10^5$）。 保证所有测试数据 $|S|$ 之和不超过 $5 \times 10^5$。

每组测试数据输出一行一个字符串表示答案。