Increasing String ~ Multiplex Coder

You are given a string

$S$ , consisting of lowercase English letters. You can do the following operation at most once :

Choose a subsequence of the string $S$ , then remove it from $S$ and concatenate the subsequence at the end of the remaining string.

Find the lexicographically minimum string that can be obtained by performing this operation at most once on $S$ .

Note that:

A string $A$ is a subsequence of a string $B$ if $A$ can be obtained by deleting several (possibly, zero or all) characters from $B$ .
Given two strings of the same length $A$ and $B$ , we say that $A$ is lexicographically smaller than $B$ if there exists an index $i$ such that $A_{1} = B_{1}, A_{2} = B_{2}, \dots, A_{i - 1} = B_{i - 1}$ and $A_{i} < B_{i}$ .

Input Format

The first line of input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a string $S$ .

Output Format

For each test case, print a single line containing the lexicographically minimum string which can be obtained from $S$ by performing the given operation at most once.

Constraints

$1 \leq T \leq 2 \cdot 10^{5}$
$1 \leq | S | \leq 10^{5}$
$S$ contains only lowercase English letters.
Sum of $| S |$ over all test cases does not exceed $10^{6}$ .

Subtasks

Subtask 1 (100 points): Original constraints

Sample Input 1

4
aba
abcd
cbcdbef
fabcdac

Sample Output 1

aab
abcd
bbccdef
aacfbcd

Explanation

Test case $1$ : It is optimal to choose the subsequence $b$ , then remove and concatenate the subsequence at the end of the remaining string $a a$ . Hence the final string is $a a + b = a a b$ .

Test case $2$ : The given string is already lexicographically minimum.

Test case $3$ : It is optimal to choose the subsequence $c c d e f$ , then remove and concatenate the subsequence at the end of the remaining string $b b$ . Hence the final string is $b b + c c d e f = b b c c d e f$ .