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

You need to perform operations on $S$ until it becomes empty. In each operation, you may perform one of the following three actions:

• 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 nonempty strings $A,B$ satisfying $S=ABA^R$, set $S=B$, and append the string $A$ to the end of $T$.

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

Find the lexicographically smallest $T$ obtainable over all sequences of operations.

Input

This problem contains multiple test cases.

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

For each test case:

One line contains a string $S$ consisting 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

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

Examples

Input 1

6
cba
zayaz
aaaaa
xazbx
ababa
aa

Output 1

abc
zaay
aaa
xabz
aaba
aa