Problem Description

You are given a string $S$ consisting of lowercase English letters, and an initially empty string $T$.

You need to perform some operations on $S$ until it becomes an empty string. Each time, you may perform one of the following three operations:

• Delete the first character of $S$ and append it to the end of $T$.
• Delete the last character of $S$ and append it to the end of $T$.
• Choose non-empty strings $A, B$ such that $S = A B A^R$. Let $S = B$, and append the string $A$ to the end of $T$.

Here, $A^R$ denotes the reverse of the string $A$.

Among all possible sequences of operations, find the lexicographically smallest $T$ that can be obtained.

Input Format

This problem contains multiple testdata.

The first line contains a positive integer $t$ ($1 \le t \le 10^5$), denoting the number of test cases.

For each test case:

Input one line containing a string $S$ of lowercase letters ($1 \le |S| \le 5 \times 10^5$).

It is guaranteed that the sum of $|S|$ over all test cases does not exceed $5 \times 10^5$.

Output Format

For each test case, output one line containing a string representing the answer.

6
cba
zayaz
aaaaa
xazbx
ababa
aa

abc
zaay
aaa
xabz
aaba
aa

Hint

Translated by ChatGPT 5