L. 博德之跃 3
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

给定一个由小写英文字母组成的字符串 $$$S$$$，以及一个初始为空的字符串 $$$T$$$。

你需要对 $$$S$$$ 执行若干次操作，直到它变为空字符串。每次你可以执行以下三种操作中的一种：

  • 删除 $$$S$$$ 的第一个字符，并将其添加到 $$$T$$$ 的末尾。
  • 删除 $$$S$$$ 的最后一个字符，并将其添加到 $$$T$$$ 的末尾。
  • 选择非空串 $$$A,B$$$ 满足 $$$S = ABA^R$$$，令 $$$S=B$$$ 并将字符串 $$$A$$$ 添加到 $$$T$$$ 的末尾。

其中 $$$A^R$$$ 表示字符串 $$$A$$$ 的反串。

求在所有操作方案中，能得到的字典序最小的 $$$T$$$。

Input

本题有多组测试数据。

输入第一行一个正整数 $$$t$$$（$$$1 \le t \le 10^5$$$），表示测试数据组数。

每组测试数据：

输入一行一个由小写字母组成的字符串 $$$S$$$（$$$1 \le |S| \le 5 \times 10^5$$$）。

保证所有测试数据 $$$|S|$$$ 之和不超过 $$$5 \times 10^5$$$。

Output

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

Example
Input
6
cba
zayaz
aaaaa
xazbx
ababa
aa
Output
abc
zaay
aaa
xabz
aaba
aa