Lexicographically Smallest String

Julia loves playing with strings. In this problem, you are given a string and you must obtain the lexicographically smallest string possible by reversing exactly one contiguous substring of the given string. Note that reversing a substring of length 1 does not change the string, and is allowed as the reversal operation.

Formally, given a string \( s \) of length \( n \), you can choose indices \( i \) and \( j \) such that \( 0 \le i < j \le n \) and reverse the substring \( s[i:j] \) (using 0-based indexing). Your task is to determine the lexicographically smallest string you can obtain by performing this operation exactly once.

For example, if \( s = \texttt{abdc} \), reversing the substring from index 2 to 3 (i.e. \( s[2:4] = \texttt{dc} \)) gives \( \texttt{abcd} \), which is the smallest possible string obtainable.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer \( T \) denoting the number of test cases.
• This is followed by \( T \) lines, each containing a single string \( s \).

outputFormat

For each test case, output on a separate line the lexicographically smallest string that can be obtained by reversing exactly one contiguous substring of the given string.

## sample

2
abdc
aabb

abcd
aabb

</p>