给定一个由小写英文字母组成的字符串 $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$。

输出格式

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

样例

输入格式 1

6
cba
zayaz
aaaaa
xazbx
ababa
aa

输出格式 1

abc
zaay
aaa
xabz
aaba
aa