Smallest Lexicographical String After Deletion

You are given a non-empty string s consisting of lowercase letters. Your task is to delete exactly one character from s so that the resulting string is the smallest possible in lexicographical order (i.e., dictionary order).

Explanation: Consider all strings that can be obtained by removing one character from s. Among all these strings, output the one which is the smallest when compared lexicographically.

One efficient solution is to iterate over the string from left to right and remove the first character that is greater than its next character. If no such character exists, remove the last character.

Note: It is allowed that the resulting string becomes empty (for example, when s is a single character).

inputFormat

The input is given in the following format from stdin:

 t
 s1
 s2
 ...
 st

Where: t is the number of test cases (an integer), and each s_i is a non-empty string consisting of lowercase letters.

outputFormat

For each test case, output the smallest lexicographical string (obtained by deleting exactly one character from the input string) on a new line to stdout.

## sample

3
abc
acbd
zyx

ab
abd
yx

</p>