Smallest String by Reversing a Substring

You are given a string. Your task is to reverse exactly one substring of the string (this can be any continuous segment, including the whole string) such that the resulting string is the lexicographically smallest possible.

Formally, for a string \(s\) of length \(n\), find indices \(i\) and \(j\) with \(0 \le i < j \le n\) such that if you reverse the substring \(s[i:j]\), the resulting string is lexicographically smallest among all possible outcomes.

Note: Although you must perform exactly one reversal, you may choose a substring whose reversal keeps the string unchanged if it is already optimal.

inputFormat

The first line contains an integer \(t\) (\(1 \le t \le 1000\)) representing the number of test cases.

Each of the following \(t\) lines contains a non-empty string \(s\) consisting of lowercase English letters.

outputFormat

For each test case, output a single line containing the lexicographically smallest string obtainable by reversing exactly one substring of the input string.

## sample

1
a

a

</p>