Background

Wandering along a quiet, deep path, you pick up fragments of memory and put them into two long pockets.

After collecting them all and pouring them out, what kind of story will they form?

Problem Description

There are two strings $S,T$. Initially, $S$ is given and $T$ is the empty string. Each time, you may perform one of the following three operations until $S$ becomes the empty string:

1. Delete the first character of $S$, and insert this character at the beginning of $T$.
2. Delete the first character of $S$, and insert this character at the end of $T$.
3. Delete the last character of $S$, and insert this character at the beginning of $T$.

a3 wants to know, after $S$ becomes the empty string, the lexicographically smallest $T$ that can be formed.

Input Format

This problem contains multiple test cases.

The first line contains an integer $Q$, which denotes the number of test cases.

For each test case, one line contains a string $S$.

Output Format

For each test case, output one line containing a string, which is the lexicographically smallest $T$ that can be formed.

2
ababdca
dcbcadb

aaabbdc
abbcdcd

Hint

[Sample 1 Explanation]

• For $\texttt{ababdca}$, perform operations of type $1,2,1,2,2,2,1$ in order, and you can obtain $\texttt{aaabbdc}$.
• For $\texttt{dcbcadb}$, perform operations of type $1,1,1,2,3,1,2$ in order, and you can obtain $\texttt{abbcdcd}$.

[Constraints and Agreements]

This problem uses bundled testdata.

• Subtask 1 (5 points): $S$ consists of at most two distinct characters.
• Subtask 2 (10 points): $\sum |S|\le 12$.
• Subtask 3 (15 points): $\sum |S|\le 100$.
• Subtask 4 (25 points): $\sum |S|\le 3\times 10^3$.
• Subtask 5 (20 points): $\sum |S|\le 2\times 10^5$.
• Subtask 6 (25 points): no special restrictions.

For $100\%$ of the data, $1\le Q\le 3\times 10^5$, $1\le |S|\le 10^6$, $1\le \sum |S|\le 2\times 10^6$, and $S$ consists only of lowercase letters.

Translated by ChatGPT 5