Smallest Lexicographical String Modification

You are given a string s consisting of lowercase English letters. You are allowed to modify at most one character of the string. Your task is to find the lexicographically smallest string that can be obtained after performing at most one modification.

In other words, if the original string is \(s\) and you modify the character at one index \(i\) (replacing \(s_i\) with another letter from 'a' to 'z', \(c \neq s_i\)), then you should choose the modification that minimizes the resulting string in lexicographical order. If no modification can produce a string smaller than the original, output the original string.

Note: Lexicographical order is defined in the usual way, where for two strings \(x\) and \(y\), \(x < y\) if in the first position where they differ, the character in \(x\) comes before the corresponding character in \(y\) in the alphabet.

inputFormat

The input is read from standard input. The first line contains a single integer \(T\) denoting the number of test cases. Each of the following \(T\) lines contains a non-empty string s consisting of only lowercase English letters.

outputFormat

For each test case, print on a separate line the lexicographically smallest string obtainable after at most one character modification.

## sample

1
abc

aac

</p>